% Notes week of 5 Nov
> module N20181105 where
> import A08Sol hiding (main)
- Generalizing generators
- always/andThen
type Gen s a = s -> (a,s)
> zero :: Gen s Int
> zero s = (0, s)
```hs
always :: a -> Gen s a
always a s = (a, s)
```
> incr :: Gen Int Int
> incr i = (i, i+1)
> fromList :: Gen [a] a
> fromList (x:xs) = (x, xs)
> fromList [] = error "fromList: ran out of elements"
> data Tree a
> = Leaf
> | Branch a (Tree a) (Tree a)
> deriving (Eq, Show)
> 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...
```hs
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:
```hs
a -> (a -> b) -> b
```
This is like an inverse function application: argument first, then
function, result.
> andThen1 :: a -> (a -> b) -> b
> andThen1 a f = f a
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:
```hs
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`?
```hs
filter :: (a -> Bool) -> [a] -> [a]
filterGen :: (a -> Bool) -> Gen s a -> Gen s a
```
------
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.
> returnMaybe :: a -> Maybe a
> returnMaybe a = Just a
> bindMaybe :: Maybe a -> (a -> Maybe b) -> Maybe b
> bindMaybe Nothing _ = Nothing
> bindMaybe (Just a) f = f a
> safeDiv :: Double -> Double -> Maybe Double
> safeDiv _ 0 = Nothing
> safeDiv x y = Just (x/y)
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.
> formulaM a b = do
> x <- safeDiv (3*a) b
> y <- safeDiv (b-1) (a+b)
> return (x+y)
Or, generalizing the division so we can substitute any monad there:
> formulaG act a b = do
> x <- act (3*a) b
> y <- act (b-1) (a+b)
> return (x+y)
```
ghci> formulaG safeDiv 3 4
Just 1.7857142857142856
ghci> formulaG (\i j -> [i,j]) 3 4
[8,13,6,11]
```
------
> main :: IO ()
> main = return ()