[Haskell-cafe] List of all powers

[Brent Yorgey]

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

> On Nov 14, 2007 1:06 PM, Brent Yorgey <byorgey at gmail.com> wrote:
> > On Nov 14, 2007 12:32 PM, Kurt Hutchinson <kelanslists at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20071114/06e25866/attachment.htm