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