import Control.Monad.State (State, evalState, get, put)
tick :: Num a => State a a
tick = do
n <- get
put $ n+1
return n
-- Using the state monad to implement dfn
data Tree a = T a [Tree a]
deriving Show
dfn :: Tree a -> Tree (a, Int)
dfn t = evalState (aux t) 1
where aux :: Tree a -> State Int (Tree (a, Int))
aux (T x ts) = do
n <- tick
ts' <- auxs ts
return $ T (x, n) ts'
auxs :: [Tree a] -> State Int [Tree (a, Int)]
auxs [] = return []
auxs (t : ts) = do
t' <- aux t
ts' <- auxs ts
return $ t' : ts'
t = T 'a' [ T 'b' []
, T 'c' [ T 'e' []
, T 'f' []
]
, T 'd' []
]
main = print $ dfn t