[Haskell-cafe] Re: [Haskell] ANN: Monad.Reader Issue 16
Edward Kmett
ekmett at gmail.com
Wed May 12 16:24:10 EDT 2010
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
More information about the Haskell-Cafe
mailing list