Re: Feedback request: priority queues in containers

On 17/03/2010, at 03:16, Louis Wasserman wrote: > I'm not willing to do this sort of typeclass wrapper thing, primarily because > nothing else in containers does -- even though we might have a Mapping type > class that handles both IntMap and Map, we don't. > > I'm inclined to let that design c

Re: Feedback request: priority queues in containers

On 17/03/2010 00:17, Louis Wasserman wrote: I tested, and this implementation actually performs better if the spine is maintained lazily, so we'll test that version. May I request that, unless there's a significant speedup from using a strict spine, that you use a lazy spine where possible.

Re: Feedback request: priority queues in containers

> > I suspect the following might be faster: > > data BinomForest2 a = Empty >| NonEmpty a [BinomTree2 a] > > data BinomTree2 a = BinomTree2 a [BinomTree2 a] > > This eliminates the "Skip" constructor, which contributes only to the > nested type guarantee. > Ehehehe. This is s

Re: Feedback request: priority queues in containers

On March 16, 2010 13:24:32 k...@cas.mcmaster.ca wrote: > Just an aside (and shameless plug ;-): Since the signatures overlap so > much, it is in fact easy to wrap these modules into instances > for many possible different type classes Yes. I can see the preferred way would be to put the classes o

Re: Feedback request: priority queues in containers

> I wrote a pretty efficient skew binomial heap implementation -- the first > step of Okasaki's approach -- and found it was already slower than the > optimized binomial heap. I'm not sure whether or not I uploaded that > benchmark, though. I'll do that at some point today, just to keep everyone

Re: Feedback request: priority queues in containers

> > I'm not sure about some of that. Imperative queues sometimes offer O(1) decreaseKey and O(lg n) delete by storing pointers to elements in a priority queue. The usual purely functional PQs can only offer O(n) decreaseKey and O(n) delete. Purely functional PSQs can offer O(lg n) decreaseKey a

Re: Feedback request: priority queues in containers

Why not use Okasaki & Brodal's "Optimal Purely Functional Priority Queues"? They offer worst case: * O(1) union, findMin, and insert * O(lg n) deleteMin The primary reason that we don't use this implementation is, quoting from the paper you yourself linked to, > Our data structure is reasonab

Re: Feedback request: priority queues in containers

> > So, it is possible to break the invariants of your priority queue by using fmap with a non-monotonic function, right? I see that it might be usefull to have such instances, sometimes. As it is not possible to hide instances, once they are definded, I'd propose to not offer those instances

Re: Feedback request: priority queues in containers

Louis Wasserman wrote: > > I'm not willing to do this sort of typeclass wrapper thing, primarily > because nothing else in containers does -- even though we might have a > Mapping type class that handles both IntMap and Map, we don't. > > I'm inclined to let that design choice stand, as f

Re: Feedback request: priority queues in containers

Hi, I think this is my first post to this list although I've been reading it for a long time. So, please, be patient with me and my post. On 03/16/2010 02:29 PM, Louis Wasserman wrote: * We offer Functor, Foldable, and Traversable instances that do not respect key ordering. All are

Re: Feedback request: priority queues in containers

> Specifically, we use a binomial heap, which offers > > O(log n) worst-case union > O(log n) worst-case extract (this in particular was a key objective of ours) > amortized O(1), worst-case O(log n) insertion. (In a persistent context, > the amortized performance bound does not necessarily hold.)

Re: Feedback request: priority queues in containers

Hi, I second that choice. There have been some attempts at using type classes, notably the Edison library, but it never got widespread. So I would follow the current containers design. Milan > I'm not willing to do this sort of typeclass wrapper thing, primarily > because nothing else in contain

Re: Feedback request: priority queues in containers

I'm not willing to do this sort of typeclass wrapper thing, primarily because nothing else in containers does -- even though we might have a Mapping type class that handles both IntMap and Map, we don't. I'm inclined to let that design choice stand, as far as containers is concerned. It would mak

Re: Feedback request: priority queues in containers

On March 16, 2010 09:29:06 Louis Wasserman wrote: > I'd like to request some more feedback on the > proposedimplementation > for priority queues in containers. Mostly, I feel like > adding a new module to containers should be contentious, and there