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

_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to