[Haskell-cafe] Re: [Haskell] ANN: Monad.Reader Issue 16

[Edward Kmett]

On Wed, May 12, 2010 at 2:12 PM, Brent Yorgey <byorgey at seas.upenn.edu>wrote:

> I am very pleased to announce that Issue 16 of The Monad.Reader is now
> available [1].
>
> Issue 16 consists of the following three articles:
>
>    * "Demand More of Your Automata" by Aran Donohue
>    * "Iteratee: Teaching an Old Fold New Tricks" by John W. Lato
>    * "Playing with Priority Queues" by Louis Wasserman
>

Great stuff.

As an aside, in "Playing with Priority Queues", Louis provides a number of
heaps but stops short of one with O(1) worst-case persistent insert.I have
an implementation of Brodal/Okasaki heaps that achieves those bounds that is
available on hackage.

http://hackage.haskell.org/package/heaps

As he notes, it does make the implementation harder to follow, but it may be
of interest for the reader who wants to dig into this space further. =)

If I have enough downtime, I'm hoping to add a functional version of
Chazelle-style soft heaps to the library as well, which gives
O(log(1/epsilon)) delete at the expense of corrupting (increasing) an
epsilon worth of the keys in your heap, which is actually quite useful for a
number of deterministic algorithms, like an O(n) median finding algorithm,
and the fast construction of minimum spanning trees.

-Edward Kmett
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100512/0ce73402/attachment.html