Definition 29 (β-normal form) Monad Class

A term that cannot be reduced any further is said to be in β-normal form. class Applicative m => Monad m where
We can think of the β-normal form as a fully executed functional program. return :: a -> m a
Divergence Example (>>=) :: ma-> (a->mb) ->mb
(λx.xx)(λx.xx) Monad Laws
True = λx.λy.x Left id: return x >>= f = f x
False = λx.λy.y Right id: mx >>= return = m
And = λp.λq.pqp Associativity: (mx >>= f) >>= g =
Or = λp.λq.ppq mx >>= (\x -> f x >>= g)
curry :: ((a, b) -> c) -> a -> b -> c Maybe monad
uncurry :: (a -> b -> c) -> (a, b) -> c --return :: a -> Maybe a
return x = Just x
Total Function
-- (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
A total function is a function that defines outputs for all possible inputs.
(>>=) m g = case m of
Partial Function
Nothing -> Nothing
A partial function is a function that is not total.
Just x -> g x
Maybe Int = {Just 0, Just 1, Just $ -1, ...} ∪ {Nothing}
Do Notation
Syntactic sugar: madd mx my =
[1,3..10] mx >>= \x ->
== enumFromThenTo 1 3 10 my >>= \y ->
== [1,3,5,7,9] return $ x+y
For example `x` `elem` xs is sugar for elem x xs, madd mx my = do x<-mx; y<- my; return $ x + y
`elem` xs is sugar for flip elem xs,
[1,2,3] is sugar for (1:2:3:[]) Applicative Class
Definition 19 (Redex) class Functor f => Applicative f where
A reducible expression or redex is any expression to which a beta- pure ::a->fa
reduction can be immediately applied. (<*>) :: f (a -> b) -> f a -> f b
Applicative Laws
Functional vs imperative
1.pure id <*> x = x
In functional programming, programs are executed by evaluating
2.pure (g x) = pure g <*> pure x
expressions, in contrast with imperative programming where programs
3.x <*> pure y = pure (\g -> g y) <*> x
are composed of statements which change global state when 4.x <*> (y <*> z)
executed.
= (pure (.) <*> x <*> y <*> z)
Purity: Return value only. No side effects (action other than returning Corollary (IMPORTANT)
values).
g <$> x = pure g <*> x
Referential transparency: the property that pure computations yield
Maybe applicative
the same value each time they are invoked instance Applicative Maybe where
Laziness: defer computation until necessary (possible due to
-- pure :: a -> Maybe a
referential transparency) pure = Just
Briefly explain how IO is considered to be pure in Haskell.
-- (<*>) :: Maybe (a->b) -> Maybe a -> Maybe b
Because the IO type is a state transformer over the state of the World, it does
Nothing <*> _ = Nothing
not admit pattern matching. Once you are in IO, you are stuck in IO. A safe (Just g) <*> mx = g <$> mx
function of the type foo :: IO a -> a does not exist – impurity is permanent
Hspec and Quickcheck Functor Class
class Functor f where
quickCheck $ \x -> x*1 == 1*x
quickCheck $ \x -> x*1 == 1*x fmap :: (a -> b) -> f a -> f b
Functor Rules
quickCheck $ \xs -> xs == reverse (reverse xs)
1. fmap id = id
Basic IO Operations 2. fmap (g.h) = fmap g . fmap h
getChar :: IO Char or equivalently
putChar :: Char -> IO() 1. (id <$>) = id
putStr :: String -> IO () 2. (g.h <$>) = (g <$>) . (h <$>)
putStrLn :: String -> IO() List Functor
read ``123`` :: Int instance Functor [] where
print = putStrLn.show -- fmap :: (a -> b) -> [a] -> [b]
addio :: IO () fmap _ [] = []
addio = do fmap f (x:xs) = f x : fmap f xs
ws <- fmap words getLine
let xs = [read w::Int|w<-ws] Higher Order Functions
print $ sum xs map :: (a->b) -> [a] -> [b]
map (2*) [1..3] == [2,4,6]
Q. Consider the following datatype for representing polynomials with integer degree
and coefficients from a: zip :: [a] -> [b] -> [(a,b)]
data Polynom a = Mono a Integer | Add (Polynom a) (Polynom a) | Mul (Polynom a) zip [1,2,3] [4,5,6] == [(1,4),(2,5),(3,6)] (shorter list used)
(Polynom a) deriving (Show, Eq) Forinstance,2x4+3x+1isgivenbyAdd (Add (Mono 2 4) zipWith :: (a->b->c) -> [a] -> [b] -> [c]
(Mono 3 1)) (Mono 1 0). Part (a) [3 marks] zipWith (+) [1,2,3] [4,5,6,7,8] == [5,7,9]
Define a functor for Polynom that maps a function over the coefficients: > (+1) <$> Add filter :: (a -> Bool) -> [a] -> [a]
(Add (Mono 2 4) (Mono 3 1)) (Mono 1 0) filter p xs = [x | x <- xs, px]
Add (Add (Mono 3 4) (Mono 4 1)) (Mono 2 0) > (/2) <$> Add (Mul (Mono 1 2) (Mono 3
all :: Foldable t => (a -> Bool) -> t a -> Bool
4)) (Mono 5 6) Add (Mul (Mono 0.5 2) (Mono 1.5 4)) (Mono 2.5 6)
(7 marks)Prove fmap id = id (i.e. the first functor law) for your functor. all odd [1,2,3,4] == Talse
data Polynom a = Mono a Integer -- this means | Add (Polynom a) (Polynom a) | Mul any :: Foldable t=> (a -> Bool) -> t a -> Bool
(Polynom a) (Polynom a) deriving (Show, Eq) -- For instance, 2x^4 + 3x + 1 is given by any odd [1,2,3,4] == True
(Add (Add (Mono 2 4) (Mono 3 1)) (Mono 1 0)) instance Functor Polynom where fmap f or odd [1,2,3,4] == True
(Mono a n) = Mono (f a) n fmap f (Add p1 p2) = Add (fmap f p1) (fmap f p2) fmap f (Mul foldr :: (a -> b -> b) -> b -> [a] -> b
p1 p2) = Mul (fmap f p1) (fmap f p2)
(7 marker) Proposition: P(x) ⇔ fmap id x = id x where x :: Polynom a. Base case: Let x = Mono (a foldr (-) 0 [1,2,3] == (1-(2-(3-0))) = 2
n) :: Polynom a. (Mono a n) : fmap id (Mono a n) = Mono (id a) n (by line 2) = Mono a n (apply foldl :: (b -> a -> b) -> b -> [a] -> b
id) = id (Mono a n) (unapply id) Thus, P(x) for any x = Mono (a n) :: Polynom a. Induction: Now,
let x = Add p1 p2 :: Polynom a and presume as the inductive hypothesis that P(p1) && P(p2). foldl (-) 0 [1,2,3] == (((0-1)-2)-3) = -6
Now consider the following case fmap id (Add p1 p2) = Add ((fmap id p1) (fmap id p2)) (by line all :: (a->Bool) -> [a] -> Bool
3) = Add (id p1) (id p2) (by inductive hypothesis) = Add p1
p2 (apply id to p1 and p2) = id (Add p1 p2) (unapply id to the
all p xs = foldl (&&) True $ map p xs
whole expression) Similar reasoning can be applied to x = Mul p1 p2:: Polynom a by replacing the length = [a] -> Int
Add with Mul in the inductive hypothesis and the subsequent deduction. Therefore, P(x) for x = length = foldr (_ n -> 1+n) 0
Add p1 p2 or x = Mul p1 p2 where p1, p2 :: Polynom a. Conclusion Therefore, by PSI, P(x) is true
for all x :: Polynom a.
Q. Considerfoo = foldl (curry fst)andrecallcurry :: ((a, b) -> c) -> a -> b -> cand Q. Suppose we have the following datatype for a tree with values in its
fst :: (a, b) -> a. Give a simpler definition of foo that does not use folding. nodes.
curry fst = const data Tree a = Leaf a | Node (Tree a) a (Tree a) Define a Functor instance for
fooQ2 x _ = x this data that does the obvious thing: apply a function to the value in each
Q. Define a function f so that node and leaf.
> :type f f :: [a] -> (b, c) -> (b -> [a] -> d) -> d data Tree a = Leaf a | Node (Tree a) a (Tree a) deriving Show
fQ1d [a] (b, c) gbas = gbas b [a] instance Functor Tree where
fmap f (Leaf a) = Leaf (f a)
Q. The Cartesian product of two lists xs and ys is given by [(x,y) | x <- xs, y <- fmap f (Node l a r) = Node (fmap f l) (f a) (fmap f r)
ys]. Use an Q. Consider the function makeUnique which removes duplicates from a list.
applicative to generate the Cartesian product of two lists. > makeUnique [1, 3, 1, 2, 2]
[1,3,2]
cprod :: [a] -> [b] -> [(a, b)] Note: The ordering of the output doesn’t matter.
cprod xs ys = pure (,) <*> xs <*> ys Part (a) [4 marks]
(map . fst) :: [(a, b)] -> [a] Define makeUnique via foo where foo is a tail recursive or iterative helper
Q. Let sum :: [Integer] -> Integer be a function that sums a list of integers. function. You may use elem :: a -> [a] -> Bool which tests list membership.
Write a useful makeUnique :: Eq a => [a] -> [a] & makeUnique [] = [] & makeUnique (x:xs)
quick-check for sum that uses a list of arbitrary length. = fooQ7 [x] xs -- fooQ7 :: [a] -> [a] -> [a] & fooQ7 ans [] = ans &fooQ7 ans
quickCheck $ \xs -> 2 * (sum xs) == sum (fmap (*2) xs) (x:xs) = fooQ7 ans' xs where ans' = if x `elem` ans then ans else ans ++ [x]
Q. Define a function which sums a list of Maybe Integer.
Q. Using a fold, write a function reverse :: String -> String that reverses a
> msum [Just 2, Just 3, Just 4] Just 9 > msum [Just 2, Nothing, Just 4] Nothing
string.
reverse' :: String -> String msum :: [Maybe Integer] -> Maybe Integer
reverse' = foldl (flip (:)) [] msum = fmap sum . sequence
Q. Implement the function Q. Consider the following datatype for representing arithmetic expressions
foo :: Integer -> IO () foo threshold = undefined that repeatedly prompts the involving multipli- cation, addition, subtraction, and the single variable X.
user to type integers until the sum of the integers strictly exceeds the data Expr = X | Num Int | BinOp Op Expr Expr deriving (Eq, Show) data Op =
threshold. Add | Mul | Subtract deriving (Eq, Show) Define a function removeSub :: Expr
Example usage in REPL: -> Expr that removes subtractions from an expression by replacing them with
> foo 3 Prompt: 1 Prompt: 2 Prompt: 1 Done -- because 1+2+1 > 3 a combination of additions and multiplications. For example,
> removeSub (BinOp Subtract (Num 100) X) BinOp Add (Num 100) (BinOp
fooQ3 :: Integer -> IO () Define a function which maps a function over a list of Maybe
Mul (Num (-1)) X) -- i.e. 100 - X = 100 + (-1) * X Do not simplify or evaluate the
a. If Nothing is in the input list the answer is Nothing: >
fooQ3 threshold = do mapMaybe (>0) [Just 1, Just 0, Just 2] Just [True,False,True] > expression.
putStr "Prompt " mapMaybe (>0) [Just 1, Nothing, Just 2] Nothing
data Expr = X | Num Int | BinOp Op Expr Expr deriving (Eq, Show) & data Op
mapMaybe :: (a -> b) -> [Maybe a] -> Maybe [b] mapMaybe
n :: Integer <- readLn fab as = if any (\x -> case x of Nothing -> True Just _ -> False) = Add | Mul | Subtract deriving (Eq, Show) & removeSub :: Expr -> Expr
if n > threshold then do as then Nothing -- else Just (fmap ((\ (Just y) -> y) . fmap fab)
&removeSub X = X & removeSub (Num n) = Num n & removeSub (BinOp
putStrLn "Done" as) else sequence (fmap (fmap fab) as) mapMaybe' :: (a ->
b) -> [Maybe a] -> Maybe [b] mapMaybe' fab as = sequence Subtract e1 e2) = & BinOp Add (removeSub e1) (BinOp Mul (Num (-1))
else do (fmap (fmap fab) as) mapMaybe'' :: (a -> b) -> [Maybe a] ->
(removeSub e2)) & removeSub (BinOp other e1 e2) = BinOp other
fooQ3 (threshold - n) Maybe [b] mapMaybe'' fab = mapM (fmap fab)
(removeSub e1) (removeSub e2)
Q. Let n 0 and f :: a -> a. The “n-fold composition of f with itself” is defined as Q. f:: (a->a->a)->a->a
f' g a = g (g a a) a
ff···f
Using the applicative for Either write a Haskell expression that adds Right 1
with f written n times and the composition operator. and Right 2 to get Right 3.
Part (a) [4 marks] pure (+) <*> Right 1 <*> Right 2
Write a function : iter n f Suppose there is an Integer in the name password which has global scope.
that returns the n-fold composition of f assuming the preconditions f :: a -> a Implement the function verify :: IO () that gives a user three tries to guess the
and n 0. password. Example usage in REPL: > password = 1234 > verify Prompt: 2
iter :: (Eq t, Num t) => t -> (b -> b) -> b -> b Prompt: 10 Prompt: 7 Failure. > verify Prompt: 1234 Success
iter 0 f = id password = "1234" verify :: IO () verify = verify' 0 verify' :: Integer -> IO ()
iter n f = f . iter (n-1) f verify' n_attempt = do if n_attempt == 3 then do putStrLn "Failure." else do
Q. Using a fold, define a function longest :: [[a]] -> [a] that returns the putStr "Prompt: " guess <- getLine if guess == password then do putStrLn
longest list among the input lists. In the event of a tie, return the list which "Success" else do verify' (n_attempt + 1)
has the least index. Write a function group :: Eq a => [a] -> [[a]] that groups adjacent equivalent
longest :: [[a]] -> [a] items in the following way
longest xs = foldr f [] xs > group [1, 1, 2, 2, 2, 3, 4, 4, 4, 1] [[1,1],[2,2,2],[3],[4,4,4],[1]] Hint: Recall the
where functions dropWhile and takeWhile of type (a -> Bool) -> [a] -> [a].
f xs ys = if length xs > length ys then xs else ys Using a fold write a function biggest :: [[a]] -> [a] to find the largest group. If
there are ties, the group with least index in the input is returned.
Removing zero or more elements from a list produces a subsequence of the > biggest $ group [1, 1, 2, 2, 2, 3, 4, 4, 4, 1] [2,2,2]
list. For example, (a) group [] = [] group (x:xs) = let hs = takeWhile (==x) (x:xs) ts = group
[1,2,3] has eight subsequences: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. (dropWhile (==x) (x:xs)) in hs : ts group' [] = [] group' (x:xs) = hs : ts where hs
Write a function lcs :: [Integer] -> [Integer] -> [Integer] that finds the longest = takeWhile (==x) (x:xs) ts = group' (dropWhile (==x) (x:xs)) -- (b) biggest [] =
com- [] biggest xss = foldl helper [] xss -- return the bigger list helper xs ys = if
mon subsequence of two lists. length xs < length ys then ys else xs
> lcs [2,1,5,1,2,3,4,1] [2,1,4,1,2,4,4] -- ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ not part of the output Write a Haskell function
[2,1,1,2,4] Break ties for longest common subsequence however you please. numSums :: Integer -> [Integer] -> Integer
Hint: Use longest here. where numSums target xs is the number of ways the target can be computed
--longest common subsequence by summing members of xs. Preconditions: The members of xs are distinct
lcs :: [Integer] -> [Integer] -> [Integer] and positive non-zero. > numSums 30 [25, 10, 5] 5 because 25+5, 10+10+10,
lcs (x:xs) (y:ys) = longest [zs | zs <- powerSet (x:xs), zs `elem` powerSet (y:ys)] 10+10+5+5, 10+5+5+5+5, and 5+5+5+5+5+5 are the comprehensive ways you
-- subseqs :: [Integer] -> [[Integer]] can make thirty from a 25, 10, and 5.
--subseqs [] = [[]] numsum :: Integer -> [Integer] -> Integer
--subseqs (x:xs) = subseqs xs ++ map (x:) (subseqs xs) numsum target xs = numsumHelper target target xs
powerSet :: [a] -> [[a]] numsumHelper :: Integer -> Integer -> [Integer] -> Integer
powerSet = foldr (\x acc -> acc ++ map (x:) acc) [[]] numsumHelper _ _ [] = 0
Define map :: (a -> b) -> [a] -> [b] using the foldr function. numsumHelper target bal (x:xs)
map' f (x:xs) = foldr (\y ys -> (f y):ys) [] (x:xs) | target == 0 = 0 -- target can't be 0
| bal < 0 = 0
unfold p h t x | p x = [] | otherwise = h x : unfold p h t (t x) | bal == 0 = 1
mapQ5b :: (a -> b) -> [a] -> [b] | otherwise = let
Define map :: (a -> b) -> [a] -> [b] using unfold. y1 = numsumHelper target (bal-x) (x:xs) y2 = numsumHelper target bal
mapQ5b f = unfold null (f.head) tail xs in y1 + y2