The*_*One 23 algorithm queue haskell list data-structures
我怎样才能有效地实现一个列表数据结构,我可以在列表的头部和末尾有2个视图,这总是指向一个列表的尾部而没有昂贵的反向调用.即:
start x = []
end x = reverse start -- []
start1 = [1,2,3] ++ start
end start1 -- [3,2,1]
end应该能够在不调用'reverse'的情况下执行此操作,而只是从列表的角度自动反向查看给定列表.如果我从连接开始创建新列表,那么同样应该成立.
Apo*_*isp 36
你可以随时使用Data.Sequence.
纯函数队列的一个众所周知的实现是使用两个列表.一个用于入队,另一个用于出队.入队将简单地纳入入队名单.Dequeue占据了出队名单的头部.当出列表列为空时,通过反转入队列表重新填充它.请参阅Chris Okasaki的纯功能数据结构.
即使这种实现方式使用reverse,其摊销时间成本也是渐进式的微不足道的.它的工作原理是,对于每个入队,你都会为出列表重新填充产生Θ(1)的时间债务.因此,出队的预期时间是入队的两倍.这是一个常数因子,因此两个操作的成本都是Θ(1).
当我google时Haskell queue，此问题在首页上显示为第三个结果，但先前提供的信息具有误导性。因此，我觉得有必要澄清一些事情。（第一个搜索结果是一个博客文章，其中包含一个粗心的实现...）
下面的所有内容基本上都来自Okasaki的论文《1995年简单高效的纯功能队列和双端队列》或他的书。
好的，让我们开始吧。
具有摊销O（1）时间复杂度的持久队列实现是可能的。诀窍是只要前部分足够长以摊销reverse操作成本，就可以反转代表队列后部分的列表。因此，当前部比后部短时，我们将其反转，而不是在前部为空时翻转后部。以下代码摘自冈崎书记的附录
data BQueue a = BQ !Int [a] !Int [a]
check :: Int -> [a] -> Int -> [a] -> BQueue a
check lenf fs lenr rs =
if lenr <= lenf
then BQ lenf fs lenr rs
else BQ (lenr+lenf) (fs ++ reverse rs) 0 []
head :: BQueue a -> a
head (BQ _ [] _ _) = error "empty queue"
head (BQ _ (x:_) _ _) = x
(|>) :: BQueue a -> a -> BQueue a
(BQ lenf fs lenr rs) |> x = check lenf fs (lenr + 1) (x:rs)
tail :: BQueue a -> BQueue a
tail (BQ lenf (x:fs) lenr rs) = check (lenf-1) fs lenr rs
而这是为什么摊销O（1）甚至用持续？Haskell很懒，因此reverse rs直到需要时才真正发生。要强制reverse rs，它必须采取| fs| 到达reverse rs。如果我们tail在达到暂停状态之前重复一次reverse rs，那么结果将被记忆，因此第二次仅需O（1）。另一方面，如果我们在放置悬架之前使用版本fs ++ reverse rs，则再次必须经过fs步骤才能到达reverse rs。冈崎的书中使用（修正的）Banker方法进行了形式化证明。
@Apocalisp的答案
当出队列表为空时，通过反转入队列表来重新填充
是他书第5章中的实现，一开始就带有警告
不幸的是，本章介绍的简单的摊销观点在存在持久性的情况下被打破了。
冈崎在第6章中描述了他摊销的O（1）持久队列。
到目前为止，我们仅讨论摊销时间的复杂性。实际上，可以完全消除摊销以实现持久队列的最坏情况O（1）时间复杂度。诀窍是 每次调用de / enqueue时都必须递增强制。但是，实际的实现在这里很难解释。reverse
同样，一切都已经在他的论文中了。