haskell - 队列的 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( n ) 时间，但我们只需为每个元素执行一次，因此我们的 get 操作平均需要 O(1) 时间：

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

你有它 - 以函数式语言摊销 O(1) FIFO 队列。

---

编辑： Efie 在评论中询问了摊销 O(1) 的性能。摊销常数时间的论点非常简单。

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

n + n + 1 + n - 1 = 3 n

我们总共进行了 2 n次调用，因此摊销时间为 3 n / 2 n = 3/2，即 O(1)。无论对ins和的调用如何get交错，相同的论点都有效 - 在两次调用中，每个元素被 cons'ed 一次，移动一次并 de-cons'ed 一次。

Answer 2

取决于您想要进行哪些操作。queuelike和dequeue包具有队列的类型类。