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.
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
On March 16, 2010 09:29:06 Louis Wasserman wrote:
I'd like to request some more feedback on the
proposedhttp://hackage.haskell.org/trac/ghc/ticket/3909implementation
for priority queues in containers. Mostly, I feel like
adding a new module to containers should be contentious, and there
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
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
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.)
Why
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
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 far as
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
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 reasonably
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
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
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 something I'm
13 matches
Mail list logo
