Difference between revisions of "PFP Laboratory 3"

From Marek Běhálek Wiki
Jump to navigation Jump to search
(Created page with "== High-order functions == * Create a function that takes a string and converts all characters to upper case letters. <syntaxhighlight lang="Haskell">allToUpper :: String ->...")
 
 
(3 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 44: Line 113:
 
</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]]
 +
</div>
 +
<div style="clear:both"></div>
 +
 +
== Operators ==
 +
*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.
 +
 +
<syntaxhighlight lang="Haskell">table :: (Bool -> Bool -> Bool) -> IO ()</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
table (\a b -> (and' a (or' a b)))                                                                             
 +
True  True  True
 +
True  False True
 +
False True  False
 +
False False False
 +
</syntaxhighlight>
 +
 +
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 +
<syntaxhighlight lang="Haskell">
 +
 +
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"
 +
</syntaxhighlight>
 +
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/GWCM50489]]
 +
</div>
 +
<div style="clear:both"></div>
 +
 +
*Extend the previously defined function to accept any number of variables (the number of variables will be given as a first parameter).
 +
 +
<syntaxhighlight lang="Haskell">tablen :: Int -> ([Bool] -> Bool) -> IO ()</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
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
 +
</syntaxhighlight>
 +
 +
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 +
<syntaxhighlight lang="Haskell">
 +
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]
 +
</syntaxhighlight>
 +
[[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!