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

问题描述

如何有效地实现一个列表数据结构，在该结构中我可以有 2 个视图来查看列表的开头和结尾，这些视图始终指向列表的开头和结尾，而无需进行昂贵的反向调用.即:

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 应该能够在不调用反向"的情况下执行此操作，而只需从列表自动反向的角度查看给定列表.如果我从串联创建新列表开始，也应该如此.

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 的 纯函数式数据结构.

Alternatively, 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 shorter than the enqueue list, refill it by reversing the enqueue list. See Chris Okasaki's Purely Functional Datastructures.

即使这个实现使用 reverse，它的摊销时间成本渐近是微不足道的.这样一来，对于每个入队，您都会因出队列表重新填充而产生 Θ(1) 的时间债务.因此，出队的预期时间最多是入队的两倍.这是一个常数因子，因此两种操作的最坏情况成本都是 O(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 at most twice that of an enqueue. This is a constant factor, so the worst-case cost of both operations is O(1).

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