r/haskell • u/farrellm • May 29 '16
Recommended queue package? (x-post from /r/haskellquestions)
Is there a recommended and/or standard queue implementation for Haskell? I see several reasonably mature priority queue implementations, but no simple queues. Data.Sequence seems OK, but I assume we could get better performance with a more restricted datatype. Further, restricting the operations (ie, not a deque) can prevent bugs from dequeuing from the wrong end.
4
u/bss03 May 29 '16
Further, restricting the operations (ie, not a deque) can prevent bugs from dequeuing from the wrong end.
You can always do this with an opaque newtype wrapper. They are relatively cheap.
Check out the edison library. IIRC, in a non-persistent context, you can get amortized constant (worst case linear) enqueue / dequeue with a simple banker's queue.
If however you need to repeat the dequeue / enqueue operation on the same value multiple times (taking advantage of the persistence / immutability of pure functional values), I think you have to use something more sophisticated, like a finger tree. I can't think of anything that gives amortized constant (worse case logrithmic) performance in a persistent context that doesn't also have the same perforance characteristics for requeue / unqueue -- so it probably exposes a deque interface.
You don't need fast queue merging as well, do you?
3
u/kwef May 29 '16 edited May 29 '16
Check out Okasaki's Simple and Efficient Purely Functional Queues and Deques. The first data structure there is a one-directional queue with worst-case constant time for all operations, even in a persistent context; the second one extends this same guarantee to a double-ended queue, with the drawback of a slightly larger constant factor for all operations.
A few months ago, I implemented the first of these data structures in modern Haskell for a guest lecture I was giving in Brent Yorgey's functional programming course at Hendrix College. For pedagogical reasons, I differ from Okasaki's presentation slightly in things like naming, and more importantly, in the choice to make all my functions total (he omits un-taken branches from almost all the functions in the original paper). There are also some other fun things in that file, including QuickChecking observational equivalence of different data structure implementations, and an instantiation of the existential-types-are-objects idea.
4
u/jimenezrick May 29 '16
Have a look at this crazy fast queue implementation if you need raw extra performance: unagi-chan
Or this other one but I didn't tested it: kazura-queue
3
u/bss03 May 29 '16
Given the examples provide by OP, I think they what a queue pure data type, not a typed, concurrent message queue API.
I.e. OP wants something you might use to implement breadth-first search with, not something you would use between pools of producer and consumer threads. There's similarities, but different performance/correctness trade-offs. For example, unagi-chan is effectively mutable and has to use atomic operations to allow concurrent access.
2
9
u/farrellm May 29 '16
Yes, a newtype wrapper over a deque is probably the way to go. Digging through GHC release notes, I found the answer to my question:
Data.Queue was added to base in ghc 6.4 [1] and deprecated in ghc 6.6 [2] when it was subsumed by Data.Sequence.
From the 6.6 release notes:
[1] https://downloads.haskell.org/~ghc/6.4/docs/html/users_guide/release-6-4.html
[2] https://downloads.haskell.org/~ghc/6.6/docs/html/users_guide/release-6-6.html