-- | A polymorphic n-ary tree data structure.
data Tree a = T a [Tree a]
deriving Show
-- | Function that annotates each node of a tree with the order in which
-- | a DFS traversal would visit it.
dfn :: Tree a -> Tree (a, Int)
dfn t = fst (aux 1 t)
where aux n (T x ts) = (T (x, n) ts', n')
where (ts', n') = auxs (n+1) ts
auxs n [] = ([], n)
auxs n (t : ts) = (t' : ts', n'')
where (t', n') = aux n t
(ts', n'') = auxs n' ts
-- | Example
t = T 'a' [ T 'b' []
, T 'c' [ T 'e' []
, T 'f' []
]
, T 'd' []
]
main = print (dfn t)