Thanks for providing this. I think this is pretty close to one of the
solutions he presents in the paper.
It seems that part of what prompted Okasaki to investigate this
further was trying to solve the problem in a strict language (ML)
after he saw a solution which relies upon laziness. What I think is
especially interesting about that is AFAICT his proposed solution
would work with an infinite tree, assuming the language supports lazy
data structures.
On Fri, Jun 25, 2010 at 11:03 AM, Thomas Horstmeyer
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