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