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