# 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)
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…

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:

            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:

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?

filter :: (a -> Bool) -> [a] -> [a]

filterGen :: (a -> Bool) -> Gen s a -> Gen s a

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

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

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)

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 ()