Thomas Horstmeyer horstmey at Mathematik.Uni-Marburg.de
Fri Jun 25 12:03:03 EDT 2010

```> How would you implement bfnum?  (If you've already read the paper,
>
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

```