[Haskell-cafe] Re: Quick question for a slow program

[apfelmus]

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