Efficient queue in Haskell



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.

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.





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).


Facebook Comments

Post a comment