monads.hs

data NumTree a b = NumNode (a, b) (Maybe [NumTree a b])
                 | NumNil
                 deriving (Eq, Show)

data Tree a = Node a (Maybe [Tree a])
            | Nil
            deriving (Eq, Show)

numberTree :: Tree a -> State Int (NumTree Int a)
numberTree Nil = return NumNil
numberTree (Node val children) = do
                                   nv <- numberNode
                                   return (NumNode (nv, val) (case children of
                                                                Nothing -> Nothing
                                                                Just a -> Just $ mapM numberTree a))
                                 where
                                   numberNode :: State (Int) Int
                                   numberNode = do
                                                  num <- get
                                                  put num + 1
                                                  return num

numTree :: Tree String -> NumTree Int String
numTree t = evalState (numberTree t) 0