Difference between revisions of "PFP Laboratory 3"

From Marek Běhálek Wiki
Jump to navigation Jump to search
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
== High-order functions ==
+
== Functions working with lists and tuples ==  
* Create a function that takes a string and converts all characters to upper case letters.
+
Implement following functions:
 +
* Create a function that merge two lists into one list of tuples.
  
<syntaxhighlight lang="Haskell">allToUpper :: String -> String</syntaxhighlight>
+
<syntaxhighlight lang="Haskell">zipThem:: [a] -> [b] -> [(a,b)]</syntaxhighlight>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
<syntaxhighlight lang="Haskell" class="myDark">
*Main> allToUpper "aAbc"
+
*Main> zipThem [1,2,3] "ABCD"
"AABC"
+
[(1,'A'),(2,'B'),(3,'C')]
 
</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">
import Data.Char
+
zipThem:: [a] -> [b] -> [(a,b)]
 
+
zipThem (x:xs) (y:ys) = (x,y) : zipThem xs ys
allToUpper :: String -> String
+
zipThem _ _ = []
allToUpper xs = [toUpper x |x<-xs]                    
 
 
 
allToUpper' :: String -> String
 
allToUpper' xs = map toUpper xs
 
 
</syntaxhighlight>
 
</syntaxhighlight>
 
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/BVU17842]]
 
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/BVU17842]]
Line 22: Line 19:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
* Implement the [https://en.wikipedia.org/wiki/Quicksort <code>quicksort</code>] algorithm. As a pivot use always the first element in the list. For dividing the list, use the function <code>filter</code>.
+
* Create a function that compute Cartesian product of two vectors.
  
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/Sj8cbRv89To]]</div>
+
<syntaxhighlight lang="Haskell">dotProduct :: [a] -> [b] -> [(a,b)]</syntaxhighlight>
<syntaxhighlight lang="Haskell">quicksort :: (Ord a) => [a] -> [a]</syntaxhighlight>
 
 
<syntaxhighlight lang="Haskell" class="myDark">
 
<syntaxhighlight lang="Haskell" class="myDark">
*Main> filter (<5) [1..10]
+
*Main> dotProduct [1..4] "ABC"
[1,2,3,4]
+
[(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>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
*Main> quicksort [1,5,3,7,9,5,2,1]
 
[1,1,2,3,5,5,7,9]
 
 
</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">
quicksort :: (Ord a) => [a] -> [a]
+
dotProduct :: [a] -> [b] -> [(a,b)]
quicksort [] = []
+
dotProduct [] _ = []
quicksort (x:xs) = let lp = filter (< x) xs
+
dotProduct (x:xs) ys = tmp ys ++ dotProduct xs ys where
                      rp = filter (>= x) xs
+
  tmp [] = []
                  in quicksort lp ++ [x] ++ quicksort rp
+
  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>
 
</syntaxhighlight>
 
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/BVU17842]]
 
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/BVU17842]]
Line 47: Line 47:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
== List comprehension ==
+
* Create a function that computes n-th number in the Fibonacci sequence. The function should use tuples in the solution.
Using the list comprehension implement following functions:
 
  
* Create a function that generates a list of all odd numbers in given interval.
+
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/Sge0DXXI36k]]</div>
<syntaxhighlight lang="Haskell">oddList :: Int -> Int -> [Int]</syntaxhighlight>
+
<syntaxhighlight lang="Haskell">fibonacci :: Int -> Int</syntaxhighlight>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
<syntaxhighlight lang="Haskell" class="myDark">
*Main> oddList 1 10 
+
*Main> fibonacci 12
[1,3,5,7,9]
+
144
 
</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]
+
fibonacci :: Int -> Int
oddList a b = [ x |x<-[a..b], odd x]
+
fibonacci n = fst (tmp n) where
 +
  fibStep (a,b) = (b,a+b)
 +
  tmp 0 = (0,1)
 +
  tmp x = fibStep (tmp (x-1))
 
</syntaxhighlight>
 
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/TXOOI93332]]
+
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/BVU17842]]
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
* Create a function that removes all upper case letters from a string.
+
== High-order functions ==
<syntaxhighlight lang="Haskell">removeAllUpper :: String -> String</syntaxhighlight>
+
* Create a function that takes a string and converts all characters to upper case letters.
 +
 
 +
<syntaxhighlight lang="Haskell">allToUpper :: String -> String</syntaxhighlight>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
<syntaxhighlight lang="Haskell" class="myDark">
*Main> removeAllUpper "ABCabcABC"
+
*Main> allToUpper "aAbc"
"abc"
+
"AABC"
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Line 77: Line 81:
 
import Data.Char
 
import Data.Char
  
removeAllUpper :: String -> String
+
allToUpper :: String -> String
removeAllUpper xs = [ x |x<-xs, not (isUpper x)]
+
allToUpper xs = [toUpper x |x<-xs]                    
</syntaxhighlight>
 
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/TXOOI93332]]
 
</div>
 
<div style="clear:both"></div>
 
  
* Create functions that computes union and intersection of two sets.
+
allToUpper' :: String -> String
<syntaxhighlight lang="Haskell">
+
allToUpper' xs = map toUpper xs
union :: Eq a => [a] -> [a] -> [a]
 
intersection :: Eq a => [a] -> [a] -> [a]
 
 
</syntaxhighlight>
 
</syntaxhighlight>
<syntaxhighlight lang="Haskell" class="myDark">
+
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/BVU17842]]
*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">
 
<syntaxhighlight lang="Haskell">
 
union :: Eq a => [a] -> [a] -> [a]
 
union xs ys = xs ++ [y| y<-ys, not (elem y xs)]
 
 
 
intersection ::  Eq a =>  [a] -> [a] -> [a]
 
intersection xs ys = [y| y<-ys, elem y xs]
 
</syntaxhighlight>
 
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/TXOOI93332]]
 
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
== More complex functions ==
+
* Implement the [https://en.wikipedia.org/wiki/Quicksort <code>quicksort</code>] algorithm. As a pivot use always the first element in the list. For dividing the list, use the function <code>filter</code>.
* Create a function that count the number of occurrences of all characters from a given string.
 
  
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/B2LFNJfC-TU]]</div>  
+
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/Sj8cbRv89To]]</div>
<syntaxhighlight lang="Haskell">countThem :: String -> [(Char, Int)]</syntaxhighlight>
+
<syntaxhighlight lang="Haskell">quicksort :: (Ord a) => [a] -> [a]</syntaxhighlight>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
<syntaxhighlight lang="Haskell" class="myDark">
*Main>countThem "hello hello hello"
+
*Main> filter (<5) [1..10]
[('h',3),('e',3),('l',6),('o',3),(' ',2)]
+
[1,2,3,4]
 
</syntaxhighlight>
 
</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                 
 
unique' [] = []
 
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>
 
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/UVITE26792]]
 
</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.
 
<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" class="myDark">
 
<syntaxhighlight lang="Haskell" class="myDark">
*Main> combinations 3 "abcdef"
+
*Main> quicksort [1,5,3,7,9,5,2,1]
["abc","abd","abe",...]
+
[1,1,2,3,5,5,7,9]
 
</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]
+
quicksort :: (Ord a) => [a] -> [a]
combinations 1 xs = [[x]| x<-xs]
+
quicksort [] = []
combinations n (x:xs) | n == length (x:xs) = [(x:xs)]
+
quicksort (x:xs) = let lp = filter (< x) xs
                      |otherwise = [[x] ++ y |y<-combinations (n-1) xs ]
+
                      rp = filter (>= x) xs
                                    ++ (combinations n xs)
+
                  in quicksort lp ++ [x] ++ quicksort rp
 
</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/BVU17842]]
 
</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!