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

[Heinrich Apfelmus]

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