# From Failures to Lists of Successes

`Monad` is a typeclass with two functions

``````class Monad m where
return :: a -> m a
(>>=)  :: m a -> (a -> m b) -> m ``````

## A `Maybe` Monad

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?

``````instance Monad Maybe where
(>>=) :: 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

Lets generalize the `Maybe` monad into a List monad!

• `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:

``````class Monad m where
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]`

## A Monad Instance for Lists

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:

``````class Monad m where
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. `[0]` B. `[0,1,4,9]` C. `[9]` 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]`

## EXERCISE: Using the List Monad

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

Generalize to `List` monad instance

• empty list is failure
• non-empty list is successes

Gives us a `for`-loop or iterator for free.