[Haskell-cafe] Leaves of a Tree

Jefferson Heard jeff at renci.org
Wed Feb 21 14:45:06 EST 2007

Alternatively, the definition of your tree could include a list of linked 
lists, one for each level of the tree.  Then you could just select the last 
list and it's the same as saving only the leaves from a complete inorder walk 
of the tree.

data AltTree a = AltTree { tree_structure :: Tree a, nodes :: [[a]] }

On Wednesday 21 February 2007 14:31, Tom Hawkins wrote:
> Hello,
> Any recommendations for speeding up extracting the set of leaves from a
> tree?
> data Tree = Branch Tree Tree | Leaf Int deriving (Eq, Ord)
> My slow, naive function:
> leaves :: Tree -> Set Int
> leaves (Leaf n) = singleton n
> leaves (Branch left right) = union (leaves left) (leaves right)
> In my case, many of the branches in the tree are the same.  I suspect
> the fixed point operation mentioned in the thread "speeding up
> fibonacci with memoizing" is applicable, but I'm having a tough time
> making the connection.
> -Tom
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

More information about the Haskell-Cafe mailing list