On Nov 14, 2007 2:57 PM, Kurt Hutchinson <kelanslists@gmail.com> wrote:

On Nov 14, 2007 1:06 PM, Brent Yorgey <byorgey@gmail.com> wrote:
> On Nov 14, 2007 12:32 PM, Kurt Hutchinson < kelanslists@gmail.com> wrote:
> The merging can be done much more simply and efficiently (this is code I
> wrote when computing squarefree numbers in a blog post a few months ago):

Wow, thanks for the tip. That really is a huge speed-up. I attempted
something like this, but just tried doing a fold of the simple merge
over the list of lists. That didn't work (not lazy enough?), which is
what sent me down the complicated path above.

Exactly. A standard fold of merges will never get around to generating any elements, since it must inspect the first element of each of the (infinitely many) lists in order to decide which is the smallest. Of course, this doesn't take advantage of the fact that the lists are guaranteed to be ordered in nondecreasing order of their first elements. mergeAll takes advantage of this by producing as many elements from the head of the first list as possible before merging. The fact that the lists are ordered by first element means that any elements from the first list which are less than the head of the second list are guaranteed to be less than everything else, and can be immediately produced as the beginning of the output list, without inspecting any more of the input lists.

-Brent