How would you implement bfnum? (If you've already read the paper, what was your first answer?)
Actually, my first thought was "Just traverse the tree twice." Then it dawned on me, that the tree could be of infinite size and I settled for the following solution: bfsn :: Tree a -> Tree Int bfsn E = E bfsn t = f [t] [] 0 where f :: [Tree a] -> [Tree a] -> Int -> Tree Int f (T _ E E : xs) ys n = T n E E f (T _ t1 E : xs) ys n = T n (f (t1:children xs) (children ys) (n + length xs + length ys + 1)) E f (T _ E t2 : xs) ys n = T n E (f (t2:children xs) (children ys) (n + length xs + length ys + 1)) f (T _ t1 t2 : xs) ys n = T n t1' t2' where t1' = f (t1:t2:children xs) (children ys) m t2' = f (t2:children xs) (children ys ++ children [t1]) (m+1) m = length xs + length ys + n + 1 children :: [Tree a] -> [Tree a] children [] = [] children (E:xs) = children xs children (T _ E E:xs) = children xs children (T _ E t2:xs) = t2:children xs children (T _ t1 E:xs) = t1:children xs children (T _ t1 t2:xs) = t1:t2:children xs One could perhaps rewrite it into something more elegant (less cases for the f-function, write children as a map), but you wanted the first answer. I am going to have a look at the paper now... Thomas