Tom Hawkins wrote:
Any recommendations for speeding up extracting
the set of leaves from a tree?
Tom,
The standard library already has this, in Data.Tree
and Data.Foldable.toList.
I'm interested to know how well that performs compared
to the roll-your-own solutions proposed so far in this
thr
Hi Tom
data Tree = Branch Tree Tree | Leaf Int deriving (Eq, Ord)
leaves :: Tree -> Set Int
leaves (Leaf n) = singleton n
leaves (Branch left right) = union (leaves left) (leaves right)
The standard method for a traversal over leaves with accumulation is:
leaves :: Tree -> Set Int
leaves x
tomahawkins:
> 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) = uni
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, n
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 m
