有人编写过一个描述FIFO队列的Haskell类型类(或者是一些类型类的组合)吗?
Data.Collection.Sequence看起来太强了,但另一方面Data.Collection.Unfoldable又太弱了(因为未定义顺序)。
我只是不想重复别人的工作。
有人编写过一个描述FIFO队列的Haskell类型类(或者是一些类型类的组合)吗?
Data.Collection.Sequence看起来太强了,但另一方面Data.Collection.Unfoldable又太弱了(因为未定义顺序)。
我只是不想重复别人的工作。
class Queue q where
empty :: q a -> Bool
get :: q a -> (a, q a)
ins :: a -> q a -> q a
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]
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)
get (F [] ys) = get (F (reverse ys) [])
get :: q a -> Maybe (a, q a)
(用Maybe
包装元组,因为如果我们无法检索第一个元素,则返回队列的其余部分就没有意义)。我忽略了这一点,以保持实现简单,所以使用我的代码时,您必须在安全使用它之前检查列表是否为空。请注意,这并不需要更多的工作,因为使用Maybe
包装器后,我们仍然必须在调用之后检查Nothing
。但是,通过包装器,我们被类型系统强制执行检查 - 如果没有它,您可以编写不安全的代码。 - Chris Taylor