On Wed, May 12, 2010 at 2:12 PM, Brent Yorgey 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

Excerpts from Brent Yorgey's message of Wed May 12 14:12:53 -0400 2010:

I am very pleased to announce that Issue 16 of The Monad.Reader is now available [1].

Excellent news! Looking forward to reading. Cheers, Edward

On 13 May 2010 04:12, Brent Yorgey wrote:

   * "Demand More of Your Automata" by Aran Donohue

Great, because of Aran I now can't change some of the bits of API in graphviz without making the code examples in his article break... -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

Brent Yorgey 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

Another great issue of my favorite Haskell magazine! I have a remark on Louis' article. Namely, I think the description of amortization is a bit unfortunate in a persistent setting like Haskell. The inc example will still take O(1) amortized time, but not because costs are saved in advance, you can't save anything when things are persistent. Imagine several clones of you coming from the future and trying to access your current bank account savings... The real reason for O(1) is that the changes to the list are lazy and the cost for the expensive operation is payed as "tax" by *future* operations that attempt to extract elements "further down" the list. This means that the amortized bound depends on the available functions for *observing* the data structure, too. Unfortunately, I think this makes the proof of theorem 27 more subtle: you need to make sure that you don't pay more than O(log n) in "tax" for evaluating the binary number with log n digits to normal form! In other words, each increment might take O(1) time but this could create so many taxes that printing all digits takes a lot longer. To demonstrate the issue, consider the function bunk :: [Bool] -> [Bool] bunk (True : bs) = False : bunk bs bunk (False : bs) = True : bunk bs bunk [] = [True] This will take O(1) time when you only look at the head of the list afterwards, i.e. head . bunk . bunk . ... . bunk $ [] is always O(n). But length . bunk . bunk . ... . bunk $ [] will take O(n^2). You'd have to show that this doesn't happen with inc . For more on how to do amortized analysis in a persistent setting, see also Okasaki's book Purely Functional Data Structures. http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf I have collected some mailing lists posts on his debit method here: http://apfelmus.nfshost.com/articles/debit-method.html Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com