My first monad tutorial

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

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