## Recap: Monad

`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
Number n) = Just n
eval (Plus e1 e2) = do n1 <- eval e1
eval (<- eval e2
n2 return (v1 + v2)
Div e1 e2) = do n1 <- eval e1
eval (<- eval e2
n2 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
instance Monad [] where
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
instance Monad [] where
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]
= bfl
bindForList
-- a
= []
bfl f [] :xs) = f x : bfl f xs
bfl f (x
-- b
= []
bfl f [] :xs) = f x ++ bfl f xs
bfl f (x
-- c
= []
bfl [] f :xs) f = f x ++ bfl f xs
bfl (x
-- d
= []
bfl [] f :xs) f = f x : bfl f xs
bfl (x
-- e
= []
bfl [] f :xs) f = x : f xs bfl (x
```

## The List Monad

Lets “run” the `>>=`

on some inputs to see how it behaves!

```
(>>=) :: [a] -> (a -> [b]) -> [b]
>>= _ = []
[] :xs) >>= f = f x ++ (xs >>= f) (x
```

`>>= f ==> [] [] `

`>>= f ==> f x3 ++ ([] >>= f) ==> f x3 [x3] `

`>>= f ==> f x2 ++ ([x3] >>= f) ==> f x2 ++ f x3 [x2,x3] `

`>>= f ==> f x1 ++ ([x2,x3] >>=f ) ==> f x1 ++ f x2 ++ f x3 [x1,x2,x3] `

## QUIZ

What does the following program evaluate to?

```
= do x <- ["cat", "dog"]
quiz <- [0, 1]
y 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?

```
= do
foo f xs <- xs
x return (f x)
= foo (\n -> n*n) [0,1,2,3] quiz
```

**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)]
= do
triples <- [0,1]
x <- [10,11]
y <- [100,101]
z []
```

**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)]
= do
pyTriples n <- ???
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] [
```

## Using the List Monad

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*.