队列的Haskell类型

Question

是否有人编写了描述FIFO队列的Haskell类型类（或者是否有类型类的组合）。

Data.Collection.Sequence似乎太强大，但另一方面Data.Collection.Unfoldable似乎太弱（顺序未定义）。

我只是想不重做别人的工作。

Answer 1

实际上，在Haskell中推出自己的FIFO队列并不难（也是一个有趣的练习）。我可以欣赏你希望为此使用标准类型类，这几乎可以肯定你应该做的。但是我刚刚在上周了解到了这一点，我很兴奋不写这些。

下面是一个简单的队列类，它允许您检查队列是否为空，从队列的头部获取第一个元素（并返回队列的其余部分）并将新元素插入到队列中。

class Queue q where 
    empty :: q a -> Bool 
    get :: q a -> (a, q a) 
    ins :: a -> q a -> q a 

做出FIFO队列的最简单方法是使用一个列表：

instance Queue [] where 
    empty = null 

    get []  = error "Can't retrieve elements from an empty list" 
    get (x:xs) = (x, xs) 

    ins x xs = xs ++ [x] 

然而，这是可怕的效率低下。如果队列当前有n元素，则插入一个新元素需要O（n）时间。如果要将m元素插入空队列，则需要花费O（m ）时间。我们可以创建一个队列来插入和检索O（1）时间内的元素（或者至少，O（1）摊销时间）？

诀窍是存储的前部和在单独的列表的队列的后面，与队列的后面被存储在反向：

data Fifo a = F [a] [a] 

instance Queue Fifo where 

队列是空的，如果正面和背面是空：

empty (F xs ys) = null xs && null ys 

要插入一个新的元素到列表中，我们只是把它放在后面的队列中，这需要O（1）次。

ins y (F xs ys) = F xs (y:ys) 

获取元素从队列的前部很容易当有等待在那里元件（以及我们抛出一个错误，如果队列为空）

get (F []  []) = error "Can't retrieve elements from an empty queue" 
    get (F (x:xs) ys) = (x, F xs ys) 

最后，如果没有元件在队列的前面等待，然后我们将队列的后面颠倒放在前面。虽然这需要O（ñ）的时候，我们只需要为每个元素做一次，所以我们get操作平均到O（1）时间：

get (F [] ys) = get (F (reverse ys) []) 

你有它 - 摊销O（ 1）以功能语言的FIFO队列。

---

编辑： EFIE问及摊销Ø在评论（1）性能。分摊恒定时间的论点非常简单。

考虑的Ñ插入到一个空队列的顺序，接着Ñ检索。插入花费时间n。在第一次检索时，队列的前面是空的，所以我们必须倒转队列的后面，这也需要时间n，再加上1来检索元素。最后，下Ñ - 1检索需要时间1中的每个，所以总时间是

Ñ + Ñ + 1 + Ñ - 1 = 3 Ñ

我们做了2 n电话总数，所以摊销时间是3 n/2 n = 3/2，这是O（1）。无论对ins和get的调用是如何交错的 - 在两个调用中，每个元素都被调用一次，移动一次并且被拒绝一次，相同的论证仍然有效。

Answer 2

取决于你想要的操作。 queuelike和dequeue包具有队列的类型类。