#3909: Priority queues in containers
-------------------------------------------+--------------------------------
Reporter: LouisWasserman | Owner: LouisWasserman
Type: feature request | Status: assigned
Priority: normal | Milestone:
Component: libraries (other) | Version: 6.12.1
Keywords: containers, priority queue | Difficulty:
Os: Unknown/Multiple | Testcase:
Architecture: Unknown/Multiple | Failure: None/Unknown
-------------------------------------------+--------------------------------
Comment(by milan):
Replying to [comment:28 LouisWasserman]:
> Yeah. When I've needed real-time performance, I'd probably do something
like
>
> {{{
> insert x $! queue
> }}}
>
> which defers the lazy work by one operation, but only by one operation.
Essentially, I'd like to be able to guarantee that {{{seq}}} actually
guarantees a fully evaluated spine, cf. Data.Map or Data.IntMap.
>
> I'm willing, though, to perhaps co-author a package for pairing heaps,
and then to recommend that package in the containers documentation as a
speedy implementation for people who are willing to settle for amortized
time bounds in exchange for overall speedy performance.
Tomorrow I am going to implement leftist-heaps, just for comparison with
binomial heaps.
If you don't mind, I would wait a bit with the pairing heaps, I want to
try to prove the complexity of the lazy variant. Maybe something will come
out of it (perhaps a different representation that would address the
"traverse in linear time" issue).
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3909#comment:29>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
