Changes between Version 1 and Version 2 of Proposals/pqueue

Show
Ignore:
Timestamp:
04/02/10 20:57:34 (5 years ago)
Author:
LouisWasserman (IP: 128.135.188.137)
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Proposals/pqueue

    v1 v2  
    7474In addition, we offer a few new methods designed to increase flexibility in manipulating the minimum element of the queue, including `getMin` (a Maybe version of `findMin`), `adjustMin` and `adjustMinWithKey` (with type analogous to `Data.Map.adjust`, except that they adjust the minimum element). 
    7575 
     76The biggest class of added methods is in methods modeled after the `take` and `takeWhile` family of Data.List methods.  The most general examples are 
     77 
     78{{{ 
     79splitAt :: Int -> MinPQueue k a -> ([(k, a)], MinPQueue k a) 
     80spanWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a) 
     81}}} 
     82 
     83In general, when we do a `take`-like method, we get an association list, and when we do a `drop`-like method, we get a queue. 
     84 
    7685Finally, we offer a number of unordered traversal methods, all of the form `xxxU` to indicate that they do not respect order.  In most cases, they are asymptotically faster than the ordered traversal methods, and the speed advantage is the primary reason to allow this violation of the priority queue abstraction. 
     86 
     87The situation for Data.PQueue.Min (and Data.PQueue.Max) is essentially analogous to Data.Set.  The most prominent change is that `foldrAsc` and `foldlDesc` methods are offered instead of a `Foldable` instance, which would be impossible due to the `Ord` constraints. 
    7788 
    7889= Important design decisions =