Difference between revisions of "PFP Laboratory 4"

From Marek Běhálek Wiki
Jump to navigation Jump to search
(Created page with "== List of lists == <div style="float: right"> 80px|link=https://youtu.be/voiTk64SaQM</div> Consider following type representing picture: <syntaxhigh...")
 
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
 +
== List comprehension ==
 +
Using the list comprehension implement following functions:
 +
 +
* Create a function that generates a list of all odd numbers in given interval.
 +
<syntaxhighlight lang="Haskell">oddList :: Int -> Int -> [Int]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> oddList 1 10 
 +
[1,3,5,7,9]
 +
</syntaxhighlight>
 +
 +
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 +
<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.
 +
<syntaxhighlight lang="Haskell">removeAllUpper :: String -> String</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> removeAllUpper "ABCabcABC"
 +
"abc"
 +
</syntaxhighlight>
 +
 +
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 +
<syntaxhighlight lang="Haskell">
 +
import Data.Char
 +
 +
removeAllUpper :: String -> String
 +
removeAllUpper xs = [ x |x<-xs, not (isUpper x)]
 +
</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.
 +
<syntaxhighlight lang="Haskell">
 +
union :: Eq a => [a] -> [a] -> [a]
 +
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">
 +
<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 style="clear:both"></div>
 +
 +
== More complex functions ==
 +
* 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>
 +
<syntaxhighlight lang="Haskell">countThem :: String -> [(Char, Int)]</syntaxhighlight>
 +
<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                 
 +
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">
 +
*Main> combinations 3 "abcdef"
 +
["abc","abd","abe",...]
 +
</syntaxhighlight>
 +
 +
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 +
<syntaxhighlight lang="Haskell">
 +
combinations :: Int -> String -> [String]
 +
combinations 1 xs = [[x]| x<-xs]
 +
combinations n (x:xs) | n == length (x:xs) = [(x:xs)]
 +
                      |otherwise = [[x] ++ y |y<-combinations (n-1) xs ]
 +
                                    ++ (combinations n xs)
 +
</syntaxhighlight>
 +
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/RTRV90066]]
 +
</div>
 +
<div style="clear:both"></div>
 +
 
== List of lists ==  
 
== List of lists ==  
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/voiTk64SaQM]]</div>  
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/voiTk64SaQM]]</div>  
Line 177: Line 288:
 
</syntaxhighlight>
 
</syntaxhighlight>
 
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/JXX12735]]
 
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/JXX12735]]
</div>
 
<div style="clear:both"></div>
 
 
== User defined data types and type classes ==
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/lo0pdwWoSx4]]</div>
 
Consider following representation of expressions
 
<syntaxhighlight lang="Haskell">
 
data Expr = Num Int
 
          | Add Expr Expr
 
          | Sub Expr Expr
 
          | Mul Expr Expr
 
          | Div Expr Expr
 
          | Var Char
 
  deriving (Eq)
 
</syntaxhighlight>
 
* Create function eval that evaluates expresions.
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/AvThE0I4Iz8]]</div>
 
<syntaxhighlight lang="Haskell">
 
eval :: Expr -> Int
 
</syntaxhighlight>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
*Main> eval (Add (Num 1) (Num 2))
 
3
 
*Main> eval (Mul (Add (Num 1) (Num 2)) (Num 3))
 
9
 
</syntaxhighlight>
 
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<syntaxhighlight lang="Haskell">
 
eval :: Expr -> Int
 
eval (Num x) = x
 
eval (Add l r) =  (eval l) + (eval r)
 
eval (Sub l r) =  (eval l) - (eval r)
 
eval (Mul l r) =  (eval l) * (eval r)
 
eval (Div l r) =  (eval l) `div` (eval r)
 
</syntaxhighlight>
 
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/BHV96059]]
 
</div>
 
<div style="clear:both"></div>
 
 
* Create function showExpr that shows expression as a String.
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/cPL1zEZHLh0]]</div>
 
<syntaxhighlight lang="Haskell">
 
showExpr :: Expr -> String
 
</syntaxhighlight>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
*Main> showExpr (Add (Num 1) (Num 2))
 
"1+2"
 
*Main> showExpr (Mul (Add (Num 1) (Num 2)) (Num 3))
 
"(1+2)*3"
 
*Main> showExpr (Mul (Add (Num 1) (Mul (Num 2) (Var 'x'))) (Mul (Num 3) (Var 'x')))
 
"(1+2*x)*3*x"
 
*Main> showExpr (Mul (Num 2) (Mul (Var 'x') (Var 'x')))                           
 
"2*x*x"
 
</syntaxhighlight>
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<syntaxhighlight lang="Haskell">
 
showExpr :: Expr -> String
 
showExpr expr = showExpr' expr NoOp
 
 
data Operation = Hi | HiDiv | Lo | LoSub | NoOp deriving (Eq)
 
 
showExpr' :: Expr -> Operation -> String
 
showExpr' (Num x) _ = show x
 
showExpr' (Var x) _ =  [x]
 
showExpr' (Add l r) op = let
 
  x = showExpr' l Lo ++"+"++showExpr' r Lo
 
  in if op == Hi || op == HiDiv || op==LoSub
 
    then "(" ++ x ++")"
 
    else x
 
showExpr' (Sub l r) op = let
 
  x = showExpr' l Lo ++"-"++showExpr' r LoSub
 
  in if op == Hi || op == HiDiv || op==LoSub
 
    then "(" ++ x ++")"
 
    else x   
 
showExpr' (Mul l r) op = let
 
  x = showExpr' l Hi ++"*"++showExpr' r Hi
 
  in if op == HiDiv
 
    then "(" ++ x ++")"
 
    else x
 
showExpr' (Div l r) op = let
 
  x = showExpr' l Hi ++"/"++showExpr' r HiDiv
 
  in if op == HiDiv
 
    then "(" ++ x ++")"
 
    else x 
 
</syntaxhighlight>
 
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/BHV96059]]
 
</div>
 
<div style="clear:both"></div>
 
 
* Extend class Show to be usable with our expressions.
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/NCAxJx_wJxI]]</div>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
*Main> Add (Num 1) (Num 2)
 
"1+2"
 
*Main> Mul (Add (Num 1) (Num 2)) (Num 3)
 
"(1+2)*3"
 
*Main> Mul (Add (Num 1) (Mul (Num 2) (Var 'x'))) (Mul (Num 3) (Var 'x'))
 
"(1+2*x)*3*x"
 
*Main> Mul (Num 2) (Mul (Var 'x') (Var 'x'))         
 
"2*x*x"
 
</syntaxhighlight>
 
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<syntaxhighlight lang="Haskell">
 
instance (Show Expr) where
 
  show = showExpr
 
</syntaxhighlight>
 
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/BHV96059]]
 
</div>
 
<div style="clear:both"></div>
 
 
* Create function derivation representing symbolic derivation of a given expression.
 
<syntaxhighlight lang="Haskell">
 
deriv :: Expr-> Char -> Expr
 
</syntaxhighlight>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
*Main> deriv (Add (Num 1) (Num 2)) 'x'
 
0+0
 
*Main> deriv (Mul (Num 2) (Mul (Var 'x') (Var 'x'))) 'x'
 
0*x*x+2*(1*x+x*1)
 
*Main> deriv (Mul (Num 2) (Mul (Var 'x') (Var 'x'))) 'x'
 
0*x*x+2*(1*x+x*1)
 
</syntaxhighlight>
 
 
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
 
<syntaxhighlight lang="Haskell">
 
deriv :: Expr-> Char -> Expr
 
deriv (Num _) _ = (Num 0)   
 
deriv (Var x) y | x==y = (Num 1)
 
                | otherwise = (Num 0)
 
deriv (Add l r) x = Add (deriv l x) (deriv r x)               
 
deriv (Sub l r) x = Sub (deriv l x) (deriv r x)
 
deriv (Mul l r) x = Add (Mul (deriv l x) r) (Mul l (deriv r x))
 
deriv (Div l r) x =
 
  Div
 
    (Sub (Mul (deriv l x) r) (Mul l (deriv r x)))
 
    (Mul r r)
 
</syntaxhighlight>
 
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/BHV96059]]
 
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>

Latest revision as of 10:58, 29 September 2022

List comprehension

Using the list comprehension implement following functions:

  • Create a function that generates a list of all odd numbers in given interval.
oddList :: Int -> Int -> [Int]
*Main> oddList 1 10   
[1,3,5,7,9]
oddList :: Int -> Int -> [Int]
oddList a b = [ x |x<-[a..b], odd x]
Try it!
  • Create a function that removes all upper case letters from a string.
removeAllUpper :: String -> String
*Main> removeAllUpper "ABCabcABC"
"abc"
import Data.Char

removeAllUpper :: String -> String
removeAllUpper xs = [ x |x<-xs, not (isUpper x)]
Try it!
  • Create functions that computes union and intersection of two sets.
union :: Eq a => [a] -> [a] -> [a]
intersection :: Eq a => [a] -> [a] -> [a]
*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]
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]
Try it!

More complex functions

  • Create a function that count the number of occurrences of all characters from a given string.
Video logo.png
countThem :: String -> [(Char, Int)]
*Main>countThem "hello hello hello"
[('h',3),('e',3),('l',6),('o',3),(' ',2)]
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]
Try it!
  • 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.
Video logo.png
combinations :: Int -> String -> [String]
*Main> combinations 3 "abcdef"
["abc","abd","abe",...]
combinations :: Int -> String -> [String]
combinations 1 xs = [[x]| x<-xs]
combinations n (x:xs) | n == length (x:xs) = [(x:xs)]
                      |otherwise = [[x] ++ y |y<-combinations (n-1) xs ] 
                                    ++ (combinations n xs)
Try it!

List of lists

Video logo.png

Consider following type representing picture:

type Pic = [String]

If you want to print this picture you can use:

pp :: Pic -> IO ()
pp x = putStr (concat (map (++"\n") x))

Picture example:

pic :: Pic
pic = [ "....#....",
        "...###...",
        "..#.#.#..",
        ".#..#..#.",
        "....#....",
        "....#....",
        "....#####"]
*Main> pp pic
....#....
...###...
..#.#.#..
.#..#..#.
....#....
....#....
....#####

Create functions that:

  • Flips picture veriticaly and horizontally.
flipV :: Pic -> Pic
flipH :: Pic -> Pic
*Main> pp(flipV pic)
....#....
...###...
..#.#.#..
.#..#..#.
....#....
....#....
#####....
*Main> pp(flipH pic)
....#####
....#....
....#....
.#..#..#.
..#.#.#..
...###...
....#....
flipV :: Pic -> Pic
flipV = map reverse 

flipV' :: Pic -> Pic
flipV' xs = [reverse x|x<-xs]

flipH :: Pic -> Pic
flipH = reverse
Try it!
  • Place one picture above another.
above :: Pic -> Pic -> Pic
*Main> pp(above pic pic)
....#....
...###...
..#.#.#..
.#..#..#.
....#....
....#....
....#####
....#....
...###...
..#.#.#..
.#..#..#.
....#....
....#....
....#####
above :: Pic -> Pic -> Pic
above x y = x ++ y
Try it!
  • Place two pictures side by side (consider, that they have the same height).
sideBySide :: Pic -> Pic -> Pic
*Main> pp(sideBySide pic pic)
....#........#....
...###......###...
..#.#.#....#.#.#..
.#..#..#..#..#..#.
....#........#....
....#........#....
....#####....#####
sideBySide :: Pic -> Pic -> Pic
sideBySide xs ys = map (\(x,y) -> x ++ y)(zip xs ys) 

sideBySide':: Pic -> Pic -> Pic
sideBySide' (x:xs) (y:ys) = (x ++ y) : sideBySide' xs ys
sideBySide' _ _ = []

sideBySide'' :: Pic -> Pic -> Pic
sideBySide'' = zipWith (++)
Try it!
  • Rotate picture to the left and to the right.
Video logo.png
rotateR :: Pic -> Pic
rotateL :: Pic -> Pic
*Main> pp(rotateR pic)       
.......
...#...
....#..
.....#.
#######
#....#.
#...#..
#..#...
#......
*Main> pp(rotateL pic)
......#
...#..#
..#...#
.#....#
#######
.#.....
..#....
...#...
.......
toRow :: String -> Pic
toRow xs = map (\x -> [x]) xs -- [[x]|x<-xs]

rotateR :: Pic -> Pic
rotateR [x] = toRow x
rotateR (x:xs) = (rotateR xs) `sideBySide` (toRow x)

rotateR' :: Pic -> Pic
rotateR' x = foldl1 sideBySide (reverse (map toRow x))


rotateL :: Pic -> Pic
rotateL [x] = reverse(toRow x)
rotateL (x:xs) = reverse(toRow x) `sideBySide` (rotateL xs)

rotateL' :: Pic -> Pic
rotateL' x = foldl1 sideBySide (map (reverse.toRow) x)
Try it!