在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 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 。

一个知名实现纯功能队列的是使用两个列表。一个用于排队和另一个用于出队。入队只会利弊的排队名单。出列取出列列表的头部。当出列列表是空的，通过颠倒排队列表填充它。见克里斯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.

尽管这个实现使用逆转，这样做的摊余时间成本是微不足道的渐近。它的工作原理出来，让每一个入队，你承担Θ（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屋！