[Haskell-cafe] Sliding Window functional data structure

[Richard O'Keefe]

Consider the following interface

	type Ord k => Sliding_Window k v

	entries :: Sliding_Window k v -> [(k,v)]
	    The cost is expected to be linear in the length of
	    the result.  The pairs are listed in increasing
	    order of k.

	add :: Ord k => k -> v -> Sliding_Window k v -> Sliding_Window k v
	    precondition: all (< k) [k' | (k',_) <- entries q]
	    The cost should be at most O((log . length . entries) q).
	    post: entries (add k v q) = entries q ++ [(k,v)]

	since :: Ord k => k -> Sliding_Window k v -> [(k,v)]
	    answers [(k',v) | (k',v) <- entries q, k' > k]
	    The cost should be at most O((log . length . entries) q
                                         + length result)

	purge :: Ord k => k -> Sliding_Window k v -> Sliding_Window k v
	    answers q' such that entries q' = [(k',v) | (k',v) <- entries q,
                                               k' > k]
	    The cost should be at most O((log . length . entries) q
					 + length [k' | (k',v) <- entries q,
							k' <= k])

Ignoring costs, this can obviously be done trivially using
a list of pairs.  Paying some attention to costs, it can also
be done using some sort of balanced search tree.  The data
structure is close to a priority queue, but subtly different.

I believe I can see how to do this in an imperative language
using a Dijkstra-style array of pairs:  add is amortised O(1)
using the well known doubling strategy, thanks to the strictly
increasing key requirement; since is a binary search followed
by a segment copy; purge is a binary search followed by nilling
out the now unwanted elements.  By adapting the back-to-back
pair of lists implementation of queues, we can obviously do
add in O(1) and purge in O(1+#deleted items) time in a pure
functional language.

Thing is, there's a baffling array of data structures to examine
(AVL, RB, 2-3, 2-3-4, 1-2-brother, finger ... trees) and I wondered
if anyone had any idea what would be particularly good for this
rather asymmetric problem.