Haskell：FIFO单子

Question

是否有针对先进先出队列的单子量（monad）的标准（或至少是常用的）程序包？我之前在一篇论文中读到了这个，并且使用过几次，但我希望停止重新实现轮子（虽然很有趣，但不划算）。

- rampion

---

相关吗？http://hackage.haskell.org/package/control-monad-queue - sclv

sclv: 非常正确！区别似乎在于使用continuations而不是将其包装在monad中。看起来我太快地接受了Sjoerd的答案。 - rampion

好的，我将其提交为答案。 - sclv

Answer 1

我认为没有其他更好的方法。我会使用一个 State 函子作为状态，其中包含 Seq 容器。

- Sjoerd Visscher

---

在根据@John L的博客文章运行了一些快速而肮脏的基准测试之后，看起来基于Seq的版本在性能上最差与rampion的gist中令人不安的Ouroboros相当。话虽如此，如果后者不能被调整为具有更好的性能，但仅使用Seq可能比说服GHC优化整个队列更少麻烦。 - C. A. McCann

另一方面，Ouroboros 队列似乎比 John L 的可变向量实现更优秀，这相当有趣。假设我没有完全搞砸我的基准测试，我怀疑应该得出的教训是可变性并非神奇地更快，聪明算法很不错，但是由非常聪明的人仔细编写的指纹树可能比任何草草拼凑的东西都要好。;] - C. A. McCann

@C.A.McCann - 我对我的结果感到惊讶，因此我请求在haskell-art上对我的可变向量实现进行代码审查，这导致了一些小的性能提升，但远远不足以超过Seq。我仍然认为我一定忽略了什么重要的东西，但是还没有人发现它。另外，如果要寻找优化版本，请参考Ouroboros作为Okasaki的初始FIFO队列。Seq可能是可比较的。 - John L

@John L：我曾多次比较不同实现方式，发现天真的纯函数版本很容易胜过基于可变状态的天真版本，所以我并不感到惊讶。无论如何，我认为Ouroboros获胜的唯一途径是GHC的积极整体程序优化，而我不认为Okasaki的实现会针对GHC进行优化，因此我怀疑这不会有太大帮助。 - C. A. McCann

带有包装数据的变异操作很耗费资源，因为会触发分代垃圾回收机制。 - augustss

Answer 2

在hackage上有一个很棒的corecursive队列版本：http://hackage.haskell.org/package/control-monad-queue

我不会说它是标准的，但它肯定反映了相当多的工作和测试。

链接的monad reader文章也是一篇非常好的阅读材料。

- sclv