From Failures to Lists of Successes

Monad is a typeclass with two functions

return :: a -> m a
(>>=)  :: m a -> (a -> m b) -> m

We can define a Maybe a type to represent “maybe-null” values

data Maybe val
= Just val        -- ^ "Just one value" :-)
| Nothing         -- ^ "No value" :-(

A the Monad instance for Maybe

Can you help me fill this in?

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing    >>= _ = ???
(Just v)   >>= f = ???

return :: a -> Result a
return v = ???

Maybe represents computations that may produce no value

A value of type Maybe a is either

• Nothing which we can think of as representing failure, or

• Just x for some x of type a, which we can think of as success

Using Maybe for computations that may produce no value

We saw how to write an eval function that doesn’t crash

• But instead gracefully returns a Nothing (if there is a div-by-zero)
eval :: Expr -> Maybe Int
eval (Number n)   = Just n
eval (Plus e1 e2) = do n1 <- eval e1
n2 <- eval e2
return (v1 + v2)
eval (Div e1 e2)  = do n1 <- eval e1
n2 <- eval e2
if n2 == 0
then Nothing
else Just (v1 `div` v2)

Replacing Failure by a List of Successes

• Nothing is the empty list []
• Just v is the singleton list [v]

… but maybe there’s something sensible for lists with many elements?

QUIZ

Lets make lists an instance of Monad by:

return :: a -> m a
(>>=)  :: m a -> (a -> m b) -> m b

return = returnForList
(>>=)  = bindForList

What must the type of returnForList be ?

A. [a]

B. a -> a

C. a -> [a]

D. [a] -> a

E. [a] -> [a]

Lets implement the Monad instance for lists?

-- returnForList :: a -> [a]
returnForList x = ???

What’s the only sensible implementation?

QUIZ

Lets make lists an instance of Monad by:

return :: a -> m a
(>>=)  :: m a -> (a -> m b) -> m b

return = returnForList
(>>=)  = bindForList

What must the type of bindForList be?

A. [a] -> [b] -> [b]

B. [a] -> (a -> b) -> [b]

C. [a] -> (a -> [b]) -> b

D. [a] -> (a -> [b]) -> [b]

E. [a] -> [b]

QUIZ

Which of the following is a valid

bindForList :: [a] -> (a -> [b]) -> [b]
bindForList = bfl

-- a
bfl f []     = []
bfl f (x:xs) = f x : bfl f xs

-- b
bfl f []     = []
bfl f (x:xs) = f x ++ bfl f xs

-- c
bfl []     f = []
bfl (x:xs) f = f x ++ bfl f xs

-- d
bfl []     f = []
bfl (x:xs) f = f x : bfl f xs

-- e
bfl []     f = []
bfl (x:xs) f = x : f xs

Lets “run” the >>= on some inputs to see how it behaves!

(>>=)  :: [a] -> (a -> [b]) -> [b]
[]         >>= _ = []
(x:xs)     >>= f = f x ++ (xs >>= f)
[] >>= f  ==> []
[x3] >>= f  ==> f x3 ++ ([] >>= f)  ==> f x3
[x2,x3] >>= f  ==> f x2 ++ ([x3] >>= f)    ==> f x2 ++ f x3
[x1,x2,x3] >>= f  ==> f x1 ++ ([x2,x3] >>=f ) ==> f x1 ++ f x2 ++ f x3

QUIZ

What does the following program evaluate to?

quiz = do x <- ["cat", "dog"]
y <- [0, 1]
return (x, y)

A. [("cat", 0)]

B. [("dog", 1)]

C. ["cat", "dog", 0, 1]

D. ["cat", 0, "dog", 1]

E. [("cat", 0), ("cat", 1), ("dog", 0), ("dog", 1)]

Whoa, behaves like a for-loop!

Lets work it out.

do {x <- ["cat", "dog"]; y <- [0, 1]; return (x, y)}

== ["cat", "dog"] >>= (\x -> [0, 1] >>= (\y -> return (x, y)))

Now lets break up the evaluation

[0, 1] >>= (\y -> [(x, y)])

==>  ((\y -> [(x, y)]) 0) ++ ((\y -> [(x, y)]) 1)

==> [(x, 0)] ++ [(x, 1)]

==> [(x, 0), (x, 1)]

So

["cat", "dog"] >>= (\x -> [(x, 0), (x, 1)])

==> (\x -> [(x, 0), (x, 1)]) "cat") ++ (\x -> [(x, 0), (x, 1)]) "dog")

==> [("cat", 0), ("cat", 1)] ++ [("dog", 0), ("dog", 1)]

==> [("cat", 0), ("cat", 1), ("dog", 0), ("dog", 1)]

QUIZ

What does quiz evaluate to?

foo f xs = do
x <- xs
return (f x)

quiz = foo (\n -> n*n)  [0,1,2,3]

A.  B. [0,1,4,9] C.  D. Type Error E. Runtime Exception

QUIZ

What does the following evaluate to?

triples :: [(Int, Int, Int)]
triples = do
x <- [0,1]
y <- [10,11]
z <- [100,101]
[]

A. [(0,10,100), (0,10,101),(1,10,100),(1,10,101),(0,11,100),(0,11,101)]

B. []

C. [[]]

D. [(0,10,100), (1,11,101)]

E. [0,1,10,100,100,101]

A Pythagorean Triple is a

• triple of positive integers a, b, c
• such that a*a + b*b = c*c

Lets implement a function to return all triples where

• a,b,c are between 0..n
pyTriples :: Int -> [(Int, Int, Int)]
pyTriples n = do
a <- ???
b <- ???
c <- ???
???

HINT: You can write [i..j] to generate the list of numbers between i and j

>>> [0..5]
[0,1,2,3,4,5]

So lets implement a function

bits :: Int -> [String]

Such that

>>> bits 0
[]
>>> bits 1
["0", "1"]
>>> bits 2
["00", "01", "10", "11"]

>>> bits 3
["000", "001", "010", "011", "100", "101", "110", "111"]

Summary

The Maybe or Result monad instance

• Conveniently work with computations that may fail