Re: [Haskell-cafe] List of all powers

On Nov 14, 2007 2:57 PM, Kurt Hutchinson wrote:

On Nov 14, 2007 1:06 PM, Brent Yorgey wrote:

...

On Nov 14, 2007 12:32 PM, Kurt Hutchinson 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