Re: [Haskell-cafe] Sliding Window functional data structure

Any search tree implementation will do add and purge in O(log n) time.

Add's obvious, but could you explain to me about purge? All of the explanations of search trees I'm familiar with, if they bother to explain deletion at all, talk about how to repair the balance of a tree after deleting *one* element. It's not at all obvious to me how to quickly rebalance an AVL tree after purging it, for example.

A finger tree will do add in O(1) and purge in O(log(min(r, n-r))) time,

Thanks for that and the sample code.