Haskell 的标准队列包？

Question

Haskell 有标准的队列实现吗？我看到几个相当成熟的优先级队列实现，但没有简单的队列。Data.Sequence 看起来不错，但我认为我们可以使用更受限制的数据类型获得更好的性能。此外，限制操作（即不是双端队列）可以防止错误从错误的一端出队。

编辑：

澄清一下，我希望有一个成熟的 Haskell 实现，最好是在 Haskell Platform 或 Hackage 中。

Answer 1

Okasaki 在他的《纯函数式数据结构》一书中将 FIFO 队列描述为一对列表，即front和back，其中 front 列表包含按正确顺序排列的队列的前面元素，back 列表包含队列的后面元素以相反的顺序。

data Queue a = Queue [a] [a]  -- front & back lists

这个想法是，新项目被插入到后列表的前面，而值从前列表中弹出。如果前面的列表变空，它将被后面的列表的相反内容替换。

队列保持不变性，只有当后列表也为空时，前列表才能为空；并执行摊销 O(1)。

-- helper function to maintain the invariance:
-- front list can be empty only if the back list is also empty
fill :: Queue a -> Queue a
fill (Queue [] b) = Queue (reverse b) []
fill q = q

push :: a -> Queue a -> Queue a
push x (Queue f b) = fill $ Queue f (x:b)

front :: Queue a -> Maybe a
front (Queue (x:_) _) = Just x
front _               = Nothing

pop :: Queue a -> Maybe (Queue a)
pop (Queue (_:xs) b) = Just . fill $ Queue xs b
pop _                = Nothing