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 <horst...@mathematik.uni-marburg.de> wrote: > >> 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe