On 2/21/07, Chad Scherrer
Tom,
I think inserting elements would be a lot faster than multiple unions. I would try:
leafList :: Tree -> [Int] leafList (Leaf n) = [n] leafList (Branch left right) = leafList left ++ leafList right
leaves = fromList . leafList
If you're writing many functions on Trees (or maybe even if you're not), you might consider writing a fold function and putting leafList in terms of this. Do you have experience with folds?
Folding was my first approach: leaves :: Tree -> Set Int leaves tree = accumLeaves Set.empty tree accumLeaves :: Set Int -> Tree -> Set Int accumLeaves set (Leaf n) = insert n set accumLeaves set (Branch l r) = foldl accumLeaves set [l,r] However, with this approach I quickly ran out of stack space. I found this odd, since I thought this program was tail recursive and shouldn't be using the stack. My next attempt was to use some form of memorization. Since many of the branches in my trees are equal, memorization should prevent following branches that have already been calculated. My question is, what is the best way to transform the original function to incorporate memorization? -Tom
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