Lanny Ripple wrote:
At least when I teased apart why the first one worked it looked
heap-like. Each step of the foldr pulled off the smallest nonprime
and merged the next two lists guaranteeing that the next smallest
nonprime would be at the head of the next step.
Well, there is heap and heap. It's true that the tree of calls to merge
fulfills the heap property, see the following diagrams:
merge before evaluation
/ \
4 merge
: / \
6 9 merge
: : / \
8 12 25 merge
: ... : / \
... 30 49 ...
: :
... ...
4 first element
:
merge
/ \
6 9
: :
8 merge
: / \
... 12 25
: :
... merge
/ \
30 49
: :
... merge
/ \
... ...
4 first and second element
:
6
:
merge
/ \
8 9
: :
... merge
/ \
12 25
: :
... merge
/ \
30 49
: :
... merge
/ \
... ...
and so on. But as you can see, the heap is not balanced, foldr1 merge
only generates a linear chain of merge nodes. A balanced tree like
merge
/ \
merge merge
/ \ / \
4 9 25 49
: : : :
... ... ... ...
would be better, except that we need a variant that with an infinite
number of leaves. The function foldTree builds such a tree.
There is also the complication that the heap "bites its own tail" in
that the multiples of a prime, and hence the heap, are not available
until the prime itself has been calculated from the heap. The People a
data structure solves this.
Regards,
apfelmus
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
