My first monad tutorial

Most books and web tutorials devote a lot of attention to deriving monads, and only briefly show how they are used in real life. For instance, here is Graham Hutton relabelling a tree with integers:

{- from Graham Hutton 'Programming in Haskell 2nd edition' 12.3 -}

type State = Int

newtype ST a = S(State -> (a,State))

app::ST a ->State ->(a,State)
app (S st) x = st x

instance Functor ST where
  fmap g st = S (\s->let (x,s') = app st s in ( g x, s'))

instance Applicative ST where 
  pure x = S (\s->(x,s))
  stf <*> stx = S (\s ->
    let (f,s') = app stf s
        (x,s'') = app stx s' in (f x, s''))

instance Monad ST where
  st >>= f = S(\s -> let (x,s') = app st s in app (f x) s')

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

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

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

tree::Tree Char
tree = Node (Node (Leaf 'a') (Leaf 'b'))(Leaf 'c')

main = print $ fst (app (mlabel tree) 0)

Bear in mind that monads are supposed to make programming easier.

Here, without confusing explanations, is how to do it in real life:

{- problem from Graham Hutton 'Programming in Haskell 2nd edition' 12.3 
   solution based on http://hackage.haskell.org/package/mtl-2.2.2/docs/Control-Monad-State-Lazy.html#g:4 -}

import Control.Monad.State

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

mlabel::Tree a -> State Int (Tree Int) 
mlabel (Leaf x) = do n<-get
                     put (n + 1)
                     return (Leaf n)
mlabel (Node l r) = do l' <- mlabel l
                       r' <- mlabel r
                       return (Node l' r')

tree::Tree Char
tree = Node (Node (Leaf 'a') (Leaf 'b'))(Leaf 'c')

main = print $ evalState (mlabel tree) 0

To be fair, I chose ‘Programming in Haskell’ as my example because it is on my bedside table. It is a clear and concise introduction to the language.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: