Re: [Haskell-cafe] Sliding Window functional data structure

[Ross Paterson]

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)

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Sliding Window functional data structure

[ok]

 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* element.
It's not at all obvious to me how to quickly rebalance an
AVL tree after purging it, for example.

 A finger tree will do add in O(1) and purge in O(log(min(r, n-r))) time,

Thanks for that and the sample code.



___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe