CS168 - 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

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

Source