Efficient queue in Haskell.

Question

How can I efficiently implement a list data structure where I can have 2 views to the head and end of the list, that always point to a head a tail of a list without expensive calls to reverse. i.e:

start x = []
end x = reverse start -- []
start1 = [1,2,3] ++ start
end start1 -- [3,2,1]

end should be able to do this without invoking 'reverse' but simply looking at the given list from the perspective of the list being in reverse automatically. The same should hold if I create new lists from concatenations to start.

Answer 1

I'm not really a Haskell user, but I found a blog post which claims to describe a Haskell queue that can be operated on in amortized constant time. It's based on a design from Chris Okasaki's excellent Purely Functional Data Structures.

Answer 2

Is Data.Dequeue what you are looking for?

(It doesn't have reverse but you can add it pretty easily and send a patch to the author.)

Answer 3

You could always just use Data.Sequence.

A well-known implementation of a purely functional queue is to use two lists. One for enqueue and another for dequeue. Enqueue would simply cons with the enqueue list. Dequeue takes the head of the dequeue list. When the dequeue list is empty, refill it by reversing the enqueue list. See Chris Okasaki's Purely Functional Datastructures.

Even though this implementation uses reverse, the amortized time cost of this is insignificant asymptotically. It works out so that for every enqueue, you incur a time debt of Θ(1) for the dequeue list refill. The expected time of a dequeue is therefore twice that of an enqueue. This is a constant factor, so the cost of both operations is Θ(1).