Thanks a lot. Yes it helps! Arnaud On Sun, Mar 4, 2012 at 9:38 PM, Joey Adams <[email protected]> wrote: > On Sun, Mar 4, 2012 at 1:27 PM, Arnaud Bailly <[email protected]> wrote: >> Hello Cafe, >> I am looking for a data structure that would have the following >> informal properties: >> - allow efficient retrieval of minimum element for some ordering >> relation on a computed property of the elements >> - allow efficient update of any element wrt to this property > > I think what you're looking for is called a "priority search queue". > It supports the operations of both a priority queue and a search tree. > Two implementations on Hackage are: > > * http://hackage.haskell.org/package/fingertree-psqueue > > * http://hackage.haskell.org/package/PSQueue > > Both libraries appear to have the same API. I'm not sure which of > these is "better". The priority search queue used by GHC's event > manager is based on PSQueue. On the other hand, fingertree-psqueue is > newer. > > In any case, a PSQ is just like a Map in that it binds keys to values. > The difference is that values are called "priorities", as you can > efficiently look up or extract the minimum value. Note that keys must > be unique (just like with Map), but priorities do not need to be. > > It appears that if you want to attach a "value" in addition to the > priority, you'll need to define a data type. E.g.: > > import Data.PSQueue (PSQ) > import Data.Unique (Unique) > > type Time = ... some efficient representation of time values ... > > data Event > = Event > { eventTimeout :: Time > , eventAction :: IO () > } > > instance Eq Event where > a == b = eventTimeout a == eventTimeout b > > instance Ord Event where > compare a b = compare (eventTimeout a) (eventTimeout b) > > type EventQueue = PSQ Unique Event > > In this case, the PSQ will be able to remove the Event whose > expiration is soonest. It will also be able to remove an Event by its > Unique key, useful for canceling Events. > > Hope this helps, > -Joey
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
