[Haskell-cafe] Re: Implementing "unionAll"

[Leon Smith]

On Thu, Feb 18, 2010 at 2:32 AM, Evan Laforge <qdunkan at gmail.com> wrote:
> By purest coincidence I just wrote the exact same function (the simple
> mergeAll', not the VIP one).  Well, extensionally the same...
> intensionally mine is 32 complicated lines and equivalent to the 3
> line mergeAll'.  I even thought of short solution by thinking that
> pulling the first element destroys the ascending lists property so
> it's equivalent to a normal sorted merge after that, and have no idea
> why I didn't just write it that way.

Well, the three line version wasn't my first implementation,  by any
stretch of the imagination.   I know I had tried to implement mergeAll
at least once,  if not two or three times before coming up with the
foldr-based implementation.   However,  I can't find any of them;
they may well be lost to the sands of time.

Incidentally,  that implementation also appears in Melissa O'Neill's
"Genuine Sieve of Eratosthenes",   in an alternate prime sieve by
Richard Bird that appears at the end.

> Anyway, I'm dropping mine and downloading data-ordlist.  Thanks for
> the library *and* the learning experience :)

Thanks!

> BTW, I notice that your merges, like mine, are left-biased.  This is a
> useful property (my callers require it), and doesn't seem to cost
> anything to implement, so maybe you could commit to it in the
> documentation?

Yes,  the description of the module explicitly states that all
functions are left-biased; if you have suggestions about how to
improve the documentation in content or organization,  I am interested
in hearing them.

Best,
Leon