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 t
> 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
On Fri, Aug 31, 2012 at 05:45:27AM +0100, Richard O'Keefe wrote:
> 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 l
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
