LabelTree.hs

import Data.Tree

type State = Int

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

apply :: ST a -> State -> (a,State)
apply (S f) x = f x

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

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

mlabel :: Tree a -> ST (Tree (a, Int))
mlabel (Node root children) = do
    n <- fresh
    return $ Node (root, n) [lab | c <- children , lab <- mlabel c]

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

testTree :: Tree String
testTree = Node "A" [Node "B" [], Node "C" [Node "D" [], Node "E" []]]