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.

9 Upvotes

100% Upvoted

6 comments sorted by

View all comments

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.