- Generalizing generators
- always/andThen

type Gen s a = s -> (a,s)

```
t1 :: Tree Char
t1 = Branch 'B' (Branch 'F' Leaf Leaf)
(Branch 'C'
(Branch 'D' Leaf Leaf)
(Branch 'E' Leaf Leaf))
```

```
applyGenToTree :: Gen s a -> Tree b -> Gen s (Tree (a,b))
applyGenToTree g Leaf s = (Leaf, s)
applyGenToTree g (Branch b l r) s0 =
(Branch (a,b) ll rr, s3)
where
(a, s1) = g s0
(ll, s2) = applyGenToTree g l s1
(rr, s3) = applyGenToTree g r s2
```

Some of the types we’ve seen that involve generators…

```
fmap :: (a -> b) -> Gen s a -> Gen s b
always :: a -> Gen s a
andThen :: Gen s a -> (a -> Gen s b) -> Gen s b
```

The `andThen`

may look confusing but take away the `Gen s`

and it’s almost nothing:

This is like an inverse function application: argument first, then function, result.

Here is how the function would be defined with `Gen s`

added back:

```
andThen :: Gen s a -> (a -> Gen s b) -> Gen s b
andThen g f s0 = (b, s2)
where
(a, s1) = g s0
(b, s2) = f a s1
```

And how we’d use it to define something like `threeRandoms`

```
threeRandoms :: Gen Seed [Int]
threeRandoms =
rand `andThen` \x1 ->
rand `andThen` \x2 ->
rand `andThen` \x3 ->
always [x1,x2,x3]
```

Wow — all the careful state-threading is now hidden! It is performed by `andThen`

but here we can treat it as “behind the scenes.”

Here’s how we’d rewrite the tree-processing using `andThen`

:

```
applyToTree g Leaf = always Leaf
applyToTree g (Branch b l r) =
g `andThen` \a ->
applyToTree g l `andThen` \ll ->
applyToTree g r `andThen` \rr ->
always (Branch (a,b) ll rr)
```

Haskell has a special syntax called “do” syntax for “Monads” which support these operations. Eventually we’d be able to turn this into:

```
applyToTree g (Branch b l r) = do
a <- g
ll <- applyToTree g l
rr <- applyToTree g r
return (Branch (a,b) ll rr)
```

Exercise? Many list operations could be defined to work on generators instead. For example, here’s the type of `filter`

. Can you write `filterGen`

?

The two monad operations:

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

The operator is called “bind”. Sometimes called “flatMap”, sometimes called “andThen”.

Maybe is a monad. Either is a monad (in the Right side). List is a monad. Gen is a monad.

Let’s define the two monad functions for Maybe.

```
bindMaybe :: Maybe a -> (a -> Maybe b) -> Maybe b
bindMaybe Nothing _ = Nothing
bindMaybe (Just a) f = f a
```

Formula: 2a/b + (a-1)/(a+b)

```
formula a b =
safeDiv (2*a) b `bindMaybe` \x ->
safeDiv (a-1) (a+b) `bindMaybe` \y ->
returnMaybe (x+y)
```

Haskell has a “do” syntax for monads.

Or, generalizing the division so we can substitute any monad there:

```
ghci> formulaG safeDiv 3 4
Just 1.7857142857142856
ghci> formulaG (\i j -> [i,j]) 3 4
[8,13,6,11]
```