[Haskell-cafe] Sliding Window functional data structure

[Okasaki, Christopher D CIV USA USMA]

One possibility would be a random-access list (http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.5156), which is a kind of list of trees.

Then 'add' is trivially O(1) and 'since' is trivially O(length result).

The only tricky operation is purge, which naively would be O(N), where N is the length of entries.  But that can be reduced using a kind of lazy deletion.  Pair the random-access list with a single k, meaning "everything <= k is considered deleted, even if it is still physically present in the data structure".  Purge would update the k and scan the list of trees, removing any tree with a root <= k.  There are only a logarithmic number of trees, so this scan would be O(log N).  In fact, it could be made O(log #remaining entries) by noting that, when one such tree is found, the list can just be chopped off there because all later trees should also be removed.

The downside of lazy deletion is that you might use a bit more space than you need, because a portion of the last tree in the list might be logically deleted but still present.  I would expect this effect to be minor in practice.

Taking this approach, there is one situation that would require clarification, and possibly special handling: If you call purge with a k that is larger than the most recent add, thereby purging everything, are you later permitted to add a k' that is smaller than the purged k?  This might be disallowed by extending the precondition of add.  But if it is allowed, then should the new k' be affected by the previous purge, or not?  It's easy to implement either way; it just depends on how you want to specify the desired behavior.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120831/21d3f37f/attachment.htm>