Skip to main content

8. Monads III

02/03/23

Recap​

If you want to be a Monad, you have to be an Applicative functor. (>>=) bind - gives you a generic way of sequencing things

The State Monad​

[Add Code]

  • State - a value which changes overtime. Key part insert a stte and modify it
  • Helper function helps streamline the code and changes S into the function.

Char -> Int Char -> ST Int [Insert Image]

Declaring States​

instance Monad ST where
    -- return :: a -> ST a
    return x = S(\s -> (x,s))

Look at the type of a, get the same type out. State is involved, but is hidden

-- (>>=) :: ST a -> (a -> ST b) -> ST b
st >>= f = S(\s -> Let(x,s') = app st s
             in app (f x) s')

Approproate form of sequencing for the state monard

Example: relabelling trees​

data Tree = Leaf a | Node (Tree a) (Tree a)

t :: Tree Char
t = Node (Node ( Leaf 'a') (Leave b')) left 'c')

Tree a -> Int -> (Tree Int, Int)

Slow way (with state)​

rlabel :: Tree a -> Int -> (Tree Int, Int)
rlabel (Leaf x) n = (Leaf n, n+1)
rlabel (Node L r) n =   (Node l' r', n'')
                where
                    (l',n') = rlabel l n
                    (r', n'') = rlabel r n'

Better way (with monads)​

fresh :: ST Int
fresh = S (\n -> (n, n+1))

mlabel :: Tree a -> ST(Tree Int)
mlabel (Leaf x) = do n <- fresh
               return (Leaf n)
mlabel (Node L r) = do L' <- mlabel L
                 r' <- mlabel r
                 return (Node L' r')

Top Level Function​

label :: Tree a -> Tree Int
label t = fst(app(mlabel t) 0)