Difference between revisions of "PFP Laboratory 3"

From Marek Běhálek Wiki
Jump to navigation Jump to search
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
== Functions working with lists and tuples ==
 +
Implement following functions:
 +
* Create a function that merge two lists into one list of tuples.
 +
 +
<syntaxhighlight lang="Haskell">zipThem:: [a] -> [b] -> [(a,b)]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> zipThem [1,2,3] "ABCD"
 +
[(1,'A'),(2,'B'),(3,'C')]
 +
</syntaxhighlight>
 +
 +
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 +
<syntaxhighlight lang="Haskell">
 +
zipThem:: [a] -> [b] -> [(a,b)]
 +
zipThem (x:xs) (y:ys) = (x,y) : zipThem xs ys
 +
zipThem _ _ = []
 +
</syntaxhighlight>
 +
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/BVU17842]]
 +
</div>
 +
<div style="clear:both"></div>
 +
 +
* Create a function that compute Cartesian product of two vectors.
 +
 +
<syntaxhighlight lang="Haskell">dotProduct :: [a] -> [b] -> [(a,b)]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> dotProduct [1..4] "ABC"
 +
[(1,'A'),(1,'B'),(1,'C'),(2,'A'),(2,'B'),(2,'C'),(3,'A'),(3,'B'),(3,'C'),(4,'A'),(4,'B'),(4,'C')]
 +
</syntaxhighlight>
 +
 +
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 +
<syntaxhighlight lang="Haskell">
 +
dotProduct :: [a] -> [b] -> [(a,b)]
 +
dotProduct [] _ = []
 +
dotProduct (x:xs) ys = tmp ys ++ dotProduct xs ys where
 +
  tmp [] = []
 +
  tmp (b:bs) = (x,b) : tmp bs
 +
 +
dotProduct' :: [a] -> [b] -> [(a,b)] 
 +
dotProduct' xs ys = [(x,y)|x<-xs, y<-ys]
 +
 +
dotProduct'' :: [a] -> [b] -> [(a,b)]
 +
dotProduct'' x y =
 +
  zip (concat (map (replicate (length y)) x))
 +
                    (concat (replicate (length x) y))
 +
</syntaxhighlight>
 +
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/BVU17842]]
 +
</div>
 +
<div style="clear:both"></div>
 +
 +
* Create a function that computes n-th number in the Fibonacci sequence. The function should use tuples in the solution.
 +
 +
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/Sge0DXXI36k]]</div>
 +
<syntaxhighlight lang="Haskell">fibonacci :: Int -> Int</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> fibonacci 12
 +
144
 +
</syntaxhighlight>
 +
 +
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 +
<syntaxhighlight lang="Haskell">
 +
fibonacci :: Int -> Int
 +
fibonacci n = fst (tmp n) where
 +
  fibStep (a,b) = (b,a+b)
 +
  tmp 0 = (0,1)
 +
  tmp x = fibStep (tmp (x-1))
 +
</syntaxhighlight>
 +
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/BVU17842]]
 +
</div>
 +
<div style="clear:both"></div>
 +
 
== High-order functions ==
 
== High-order functions ==
 
* Create a function that takes a string and converts all characters to upper case letters.
 
* Create a function that takes a string and converts all characters to upper case letters.
Line 47: Line 116:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
== List comprehension ==  
+
== Operators ==  
Using the list comprehension implement following functions:
+
*Define following functions that performs corresponding logic operations: <code>not', and', or', nand', xor', impl', equ'</code>
 +
*Define the 'standard' priority for all these functions, if they are used as operators.
 +
*Create a function that prints the truth table of a given logical expression for two variables.
  
* Create a function that generates a list of all odd numbers in given interval.
+
<syntaxhighlight lang="Haskell">table :: (Bool -> Bool -> Bool) -> IO ()</syntaxhighlight>
<syntaxhighlight lang="Haskell">oddList :: Int -> Int -> [Int]</syntaxhighlight>
 
 
<syntaxhighlight lang="Haskell" class="myDark">
 
<syntaxhighlight lang="Haskell" class="myDark">
*Main> oddList 1 10 
+
table (\a b -> (and' a (or' a b)))                                                                             
[1,3,5,7,9]
+
True  True  True
 +
True  False True
 +
False True  False
 +
False False False
 
</syntaxhighlight>
 
</syntaxhighlight>
  
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<syntaxhighlight lang="Haskell">
 
<syntaxhighlight lang="Haskell">
oddList :: Int -> Int -> [Int]
 
oddList a b = [ x |x<-[a..b], odd x]
 
</syntaxhighlight>
 
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/TXOOI93332]]
 
</div>
 
<div style="clear:both"></div>
 
  
* Create a function that removes all upper case letters from a string.
+
not' :: Bool -> Bool
<syntaxhighlight lang="Haskell">removeAllUpper :: String -> String</syntaxhighlight>
+
not' True = False
<syntaxhighlight lang="Haskell" class="myDark">
+
not' False = True
*Main> removeAllUpper "ABCabcABC"
+
infixl 5 `not'`
"abc"
 
</syntaxhighlight>
 
  
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
+
and' :: Bool -> Bool -> Bool
<syntaxhighlight lang="Haskell">
+
and' True True = True
import Data.Char
+
and' _ _ = False
 +
infixl 4 `and'`
  
removeAllUpper :: String -> String
+
or' :: Bool -> Bool -> Bool
removeAllUpper xs = [ x |x<-xs, not (isUpper x)]
+
or' False False = False
</syntaxhighlight>
+
or' _ _ = True
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/TXOOI93332]]
+
infixl 3 `or'`
</div>
 
<div style="clear:both"></div>
 
  
* Create functions that computes union and intersection of two sets.
+
nand' :: Bool -> Bool -> Bool
<syntaxhighlight lang="Haskell">
+
nand' x y = not' (and' x y)
union :: Eq a => [a] -> [a] -> [a]
+
infixl 4 `nand'`
intersection :: Eq a => [a] -> [a] -> [a]
 
</syntaxhighlight>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
*Main> union [1..5] [3..10]
 
[1,2,3,4,5,6,7,8,9,10]
 
*Main> intersection [1..5] [3..10]
 
[3,4,5]
 
</syntaxhighlight>
 
  
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
+
xor' :: Bool -> Bool -> Bool
<syntaxhighlight lang="Haskell">
+
xor' x y = x/=y
union :: Eq a => [a] -> [a] -> [a]
+
infixl 3 `xor'`
union xs ys = xs ++ [y| y<-ys, not (elem y xs)]
 
  
intersection :: Eq a =>  [a] -> [a] -> [a]
+
impl' :: Bool -> Bool -> Bool
intersection xs ys = [y| y<-ys, elem y xs]
+
impl' True False = False
</syntaxhighlight>
+
impl' _ _ = True
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/TXOOI93332]]
+
infixl 2 `impl'`
</div>
 
<div style="clear:both"></div>
 
  
== More complex functions ==  
+
equ' :: Bool -> Bool -> Bool
* Create a function that count the number of occurrences of all characters from a given string.
+
equ' x y = x == y
 +
infixl 7 `equ'`
  
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/B2LFNJfC-TU]]</div>  
+
table :: (Bool -> Bool -> Bool) -> IO ()
<syntaxhighlight lang="Haskell">countThem :: String -> [(Char, Int)]</syntaxhighlight>
+
table expr = putStr (concat [nicePrint [x,y,(expr x y)] |x<-[True,False], y<-[True,False]])
<syntaxhighlight lang="Haskell" class="myDark">
 
*Main>countThem "hello hello hello"
 
[('h',3),('e',3),('l',6),('o',3),(' ',2)]
 
</syntaxhighlight>
 
 
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<syntaxhighlight lang="Haskell">
 
unique :: String -> String
 
unique n = reverse(tmp n "") where
 
  tmp [] store = store
 
  tmp (x:xs) store | x `elem` store = tmp xs store
 
                  | otherwise = tmp xs (x:store)
 
  
unique' :: String -> String                 
+
nicePrint :: [Bool] -> String
unique' [] = []
+
nicePrint xs = concat [show x++"\t"| x<-xs] ++ "\n"
unique' (x:xs) = x: unique' (filter (/=x)xs)
 
 
 
countThem :: String -> [(Char, Int)]
 
countThem xs = let u = unique xs
 
              in [(x, length (filter (==x) xs)) |x<-u]
 
 
</syntaxhighlight>
 
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/UVITE26792]]
+
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/GWCM50489]]
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
* Create a function that generates all combinations of given length from the characters from given string. You can assume, that all character are unique and the given length is not bigger then the length of this string.
+
*Extend the previously defined function to accept any number of variables (the number of variables will be given as a first parameter).
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/-muPoJucLyI]]</div>
+
 
<syntaxhighlight lang="Haskell">combinations :: Int -> String -> [String]</syntaxhighlight>
+
<syntaxhighlight lang="Haskell">tablen :: Int -> ([Bool] -> Bool) -> IO ()</syntaxhighlight>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
<syntaxhighlight lang="Haskell" class="myDark">
*Main> combinations 3 "abcdef"
+
tablen 3 (\[a,b,c] -> a `and'` (b `or'` c) `equ'` a `and'` b `or'` a `and'` c)
["abc","abd","abe",...]
+
True  True  True  => True
 +
True  True  False  => True
 +
True  False  True  => True
 +
True  False  False  => False
 +
False  True  True  => False
 +
False  True  False  => False
 +
False  False  True  => False
 +
False  False  False  => False
 
</syntaxhighlight>
 
</syntaxhighlight>
  
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<syntaxhighlight lang="Haskell">
 
<syntaxhighlight lang="Haskell">
combinations :: Int -> String -> [String]
+
tablen :: Int -> ([Bool] -> Bool) -> IO ()
combinations 1 xs = [[x]| x<-xs]
+
tablen n f = putStr(concat [nicePrint x ++ " => " ++ show(f x) ++ "\n" |x<-allValues n]) where
combinations n (x:xs) | n == length (x:xs) = [(x:xs)]
+
  allValues 1 = [[True], [False]]
                      |otherwise = [[x] ++ y |y<-combinations (n-1) xs ]  
+
  allValues n = [x:y| x<-[True,False], y<-allValues (n-1)]
                                    ++ (combinations n xs)
+
 
 +
  nicePrint :: [Bool] -> String
 +
  nicePrint xs = concat [show x++"\t"| x<-xs]
 
</syntaxhighlight>
 
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/RTRV90066]]
+
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/IDZIG48578]]
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>

Latest revision as of 10:57, 29 September 2022

Functions working with lists and tuples

Implement following functions:

  • Create a function that merge two lists into one list of tuples.
zipThem:: [a] -> [b] -> [(a,b)]
*Main> zipThem [1,2,3] "ABCD"
[(1,'A'),(2,'B'),(3,'C')]
zipThem:: [a] -> [b] -> [(a,b)]
zipThem (x:xs) (y:ys) = (x,y) : zipThem xs ys
zipThem _ _ = []
Try it!
  • Create a function that compute Cartesian product of two vectors.
dotProduct :: [a] -> [b] -> [(a,b)]
*Main> dotProduct [1..4] "ABC"
[(1,'A'),(1,'B'),(1,'C'),(2,'A'),(2,'B'),(2,'C'),(3,'A'),(3,'B'),(3,'C'),(4,'A'),(4,'B'),(4,'C')]
dotProduct :: [a] -> [b] -> [(a,b)]
dotProduct [] _ = []
dotProduct (x:xs) ys = tmp ys ++ dotProduct xs ys where
  tmp [] = []
  tmp (b:bs) = (x,b) : tmp bs

dotProduct' :: [a] -> [b] -> [(a,b)]  
dotProduct' xs ys = [(x,y)|x<-xs, y<-ys]

dotProduct'' :: [a] -> [b] -> [(a,b)]
dotProduct'' x y = 
  zip (concat (map (replicate (length y)) x))
                     (concat (replicate (length x) y))
Try it!
  • Create a function that computes n-th number in the Fibonacci sequence. The function should use tuples in the solution.
Video logo.png
fibonacci :: Int -> Int
*Main> fibonacci 12
144
fibonacci :: Int -> Int
fibonacci n = fst (tmp n) where
  fibStep (a,b) = (b,a+b)
  tmp 0 = (0,1)
  tmp x = fibStep (tmp (x-1))
Try it!

High-order functions

  • Create a function that takes a string and converts all characters to upper case letters.
allToUpper :: String -> String
*Main> allToUpper "aAbc"
"AABC"
import Data.Char

allToUpper :: String -> String
allToUpper xs = [toUpper x |x<-xs]                     

allToUpper' :: String -> String
allToUpper' xs = map toUpper xs
Try it!
  • Implement the quicksort algorithm. As a pivot use always the first element in the list. For dividing the list, use the function filter.
Video logo.png
quicksort :: (Ord a) => [a] -> [a]
*Main> filter (<5) [1..10]
[1,2,3,4]
*Main> quicksort [1,5,3,7,9,5,2,1]
[1,1,2,3,5,5,7,9]
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = let lp = filter (< x) xs
                       rp = filter (>= x) xs
                   in quicksort lp ++ [x] ++ quicksort rp
Try it!

Operators

  • Define following functions that performs corresponding logic operations: not', and', or', nand', xor', impl', equ'
  • Define the 'standard' priority for all these functions, if they are used as operators.
  • Create a function that prints the truth table of a given logical expression for two variables.
table :: (Bool -> Bool -> Bool) -> IO ()
table (\a b -> (and' a (or' a b)))                                                                              
True  True  True
True  False True
False True  False
False False False
not' :: Bool -> Bool
not' True = False
not' False = True
infixl 5 `not'` 

and' :: Bool -> Bool -> Bool
and' True True = True
and' _ _ = False
infixl 4 `and'` 

or' :: Bool -> Bool -> Bool
or' False False = False
or' _ _ = True
infixl 3 `or'` 

nand' :: Bool -> Bool -> Bool
nand' x y = not' (and' x y)
infixl 4 `nand'` 

xor' :: Bool -> Bool -> Bool
xor' x y = x/=y
infixl 3 `xor'` 

impl' :: Bool -> Bool -> Bool
impl' True False = False
impl' _ _ = True
infixl 2 `impl'` 

equ' :: Bool -> Bool -> Bool
equ' x y = x == y
infixl 7 `equ'` 

table :: (Bool -> Bool -> Bool) -> IO ()
table expr = putStr (concat [nicePrint [x,y,(expr x y)] |x<-[True,False], y<-[True,False]])

nicePrint :: [Bool] -> String
nicePrint xs = concat [show x++"\t"| x<-xs] ++ "\n"
Try it!
  • Extend the previously defined function to accept any number of variables (the number of variables will be given as a first parameter).
tablen :: Int -> ([Bool] -> Bool) -> IO ()
 tablen 3 (\[a,b,c] -> a `and'` (b `or'` c) `equ'` a `and'` b `or'` a `and'` c)
True   True   True   => True
True   True   False  => True
True   False  True   => True
True   False  False  => False
False  True   True   => False
False  True   False  => False
False  False  True   => False
False  False  False  => False
tablen :: Int -> ([Bool] -> Bool) -> IO ()
tablen n f = putStr(concat [nicePrint x ++ " => " ++ show(f x) ++ "\n" |x<-allValues n]) where 
  allValues 1 = [[True], [False]]
  allValues n = [x:y| x<-[True,False], y<-allValues (n-1)]

  nicePrint :: [Bool] -> String
  nicePrint xs = concat [show x++"\t"| x<-xs]
Try it!