In my experience, bankers' Queues (like the one presented in the article) are <i>not</i> the best persistent queue solution.<p>The Finger Tree (available in the Haskell standard library under Data.Sequence) is a really impressive data structure. It's persistent, it has O(log(min(n,len-n))) access and modification (which means O(1) cons, snoc, head, and last), and O(log(min(m,n))) concatenation.<p>In my testing, it was several times faster than the fastest banker's queue library I found.
I probably understand these concepts without knowing their official names. But man, sometimes I feel really dumb when I see phrases like "Queue Invariant" or "Amortised Complexity". It's nice that this article explains them simply.
Never thought lazyness could transform an o(1) operation into an o(n) as a side effect.<p>I thought memory management was hard to reason about in pure functional languages, but i never thought it could affect algorithmic complexity this badly.