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.