[Haskell-cafe] Sliding Window functional data structure
Richard O'Keefe
ok at cs.otago.ac.nz
Fri Aug 31 06:45:27 CEST 2012
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.
More information about the Haskell-Cafe
mailing list