Sliding Window functional data structure - Haskell-cafe

The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion Sliding Window functional data structure
Received-SPF: pass (google.com: best guess record for domain of haskell-cafe-boun...@haskell.org designates 2a01:4f8:121:6::10 as permitted sender) client-ip=2a01:4f8:121:6::10;
Date: Fri, 31 Aug 2012 09:03:52 +0100
From: Ross Paterson <r...@soi.city.ac.uk>
To: haskell-c...@haskell.org
Message-ID: <20120831080352.GA3...@soi.city.ac.uk>
Mail-Followup-To: haskell-c...@haskell.org
References: <59ACDFB2-2839-43FF-93F1-5BB3575A3...@cs.otago.ac.nz>
MIME-Version: 1.0
Content-Disposition: inline
In-Reply-To: <59ACDFB2-2839-43FF-93F1-5BB3575A3...@cs.otago.ac.nz>
User-Agent: Mutt/1.5.21 (2010-09-15)
Subject: Re: [Haskell-cafe] Sliding Window functional data structure
Precedence: list
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Sender: haskell-cafe-boun...@haskell.org
Errors-To: haskell-cafe-boun...@haskell.org

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-C...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
Account Options
