[Haskell-cafe] Sliding Window functional data structure
Ross Paterson
ross at soi.city.ac.uk
Fri Aug 31 10:03:52 CEST 2012
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 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])
Any search tree implementation will do add and purge in O(log n) time.
A finger tree will do add in O(1) and purge in O(log(min(r, n-r))) time,
where r in the length of the result.
{-# LANGUAGE MultiParamTypeClasses #-}
module SlidingWindow where
import Data.FingerTree
import Data.Foldable
import Data.Monoid
data Entry k v = Entry k v
data Max k = Bot | Lift k
deriving (Eq, Ord)
instance Ord k => Monoid (Max k) where
mempty = Bot
mappend = max
instance Ord k => Measured (Max k) (Entry k v) where
measure (Entry k _) = Lift k
newtype SlidingWindow k v = SW (FingerTree (Max k) (Entry k v))
entries :: SlidingWindow k v -> [(k,v)]
entries (SW t) = [(k, v) | Entry k v <- toList t]
emptySW :: Ord k => SlidingWindow k v
emptySW = SW empty
add :: Ord k => k -> v -> SlidingWindow k v -> SlidingWindow k v
add k v (SW t) = SW (t |> Entry k v)
since :: Ord k => k -> SlidingWindow k v -> [(k,v)]
since k = entries . purge k
purge :: Ord k => k -> SlidingWindow k v -> SlidingWindow k v
purge k (SW t) = SW (dropUntil (> Lift k) t)
More information about the Haskell-Cafe
mailing list