Haskell队列类型类

Question

Haskell队列类型类

haskelltypeclass

6

有人编写过一个描述FIFO队列的Haskell类型类（或者是一些类型类的组合）吗？

Data.Collection.Sequence看起来太强了，但另一方面Data.Collection.Unfoldable又太弱了（因为未定义顺序）。

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

- Clinton

2个回答

2

根据您需要的操作而定。 queuelike 和 dequeue 包含有关于队列的类型类。

- Daniel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Chris Taylor · Accepted Answer

实际上，在Haskell中自己编写FIFO队列并不太难(也是一个有趣的练习)。我可以理解你想要使用标准类型类来完成这个操作，这很可能是你应该采取的方法。但我上周才学会这个，我实在太兴奋了，不能不写一下。

这里有一个简单的队列类，允许您检查队列是否为空，从队列头部获取第一个元素(并返回其余的队列)，并插入新元素到队列中。

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

最简单的创建先进先出（FIFO）队列的方法是使用列表（list）：

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^2)的时间。我们能否创建一个在O(1)时间（或至少是O(1)摊销时间）内插入和检索元素的队列呢？

技巧在于将队列的前端和后端分别存储在不同的列表中，其中队列的后端以相反的顺序存储：

data Fifo a = F [a] [a]

instance Queue Fifo where

如果队列的前面和后面都为空，则队列为空：

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

要在列表中插入新元素，我们只需将其append（cons）到队列的末尾，这需要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) 的时间，但对于每个元素，我们只需要执行一次，因此我们的获取操作平均而言只需要 O(1) 的时间：

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

这里就是函数式语言中的摊销O(1)先进先出队列。修改：在评论中，Efie问到了摊销O(1)的性能。关于摊销常数时间的论证非常简单。考虑将n个元素插入空队列，随后又取出n个元素。插入需要n次，第一次取出时，队列的前端为空，所以我们必须反转队列的后端，这也需要n次，加上1次检索元素。最后，接下来的n-1个检索每次只需要1次，因此总时间为n+n+1+n-1=3n。我们总共进行了2n个调用，因此摊销时间是3n/2n=3/2，即O(1)。无论如何，每个元素都会在两个调用中被cons一次、移动一次和de-cons一次，这个论点同样适用于对ins和get的调用如何交错的情况。