Haskell中的高效队列 [英] Efficient queue in Haskell

问题描述

如何有效地实现一个列表数据结构，我可以在列表的头部和末尾有两个视图，这总是指向列表的尾部，而不需要昂贵的电话来反转。
ie：

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.

推荐答案

您可以随时使用 Data.Sequence 。

纯功能队列的一个众所周知的实现是使用两个列表。一个用于排队，另一个用于排队。入队将简单地排除入队列表。出队取出出列表的头。当出队列表为空时，通过反转入队列表来重新填充。见Chris Okasaki的纯功能数据结构。

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.

即使这个实现使用 reverse ，这个的摊销时间成本是渐近渐近的。它的出发点是，对于每一个排队，你都需要一个时间债务Θ（1）用于出队列表的再填充。因此，出队的预期时间是入队的两倍。这是一个常数因素，所以两种操作的成本都是Θ（1）。

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

这篇关于Haskell中的高效队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！