writer monad 对列表的效率如何？

Question

Haskell writer monad 在列表 (Writer [w] a) 上的实现将使用 ++ 添加项目。因此，如果我在列表编写器 monad 中编写此代码：

do
  tell [a, b, c]
  tell [d]

列表将附加 [a, b, c] ++ [d]。在使用 OCaml 之后，我已经内化了应该使用 cons 运算符 (:) 而不是连接运算符 (++) 来构建列表，因为后者在其第一个参数中是 O(n)。

我的工作负载一次向 writer monad 添加一条“消息”，因此 ++ 的第二个参数通常是一个单例列表。

在 Haskell 中，懒惰会使列表编写器 monad 比 OCaml 这样的热切语言更高效吗？如果不是，对于我的工作量来说，什么是有效的替代方案？

Answer 1

左关联 (++) 效率低下，因为最左边的列表被遍历多次，每个包含 (++) 一次。右关联 (++) 很好（至少不能通过直接使用 (:) 来提高效率）。

标准 WriterT 转换器（和 (,) 编写器）将它们的调用关联到 (++) 的方式与它们的绑定关联的方式相同。因此，通过前面讨论的扩展，左关联的 (>>=)s 将有问题，而右关联的则没问题。特别是，这意味着存在 抽象成本 。如果在重构中，要提取下面 do 块的前两行：

x = do
    tell a
    tell b
    tell c

放入一个单独的定义中，也许是因为它们经常发生：

y = do
    tell a
    tell b

x = do
    y
    tell c

此重构将一个绑定重新关联到左侧，因此成本略高。

如果这让您担心，您可以通过使用标准差异列表技巧作为您的幺半群来选择稍微不同的权衡。所以：

do
    tell (Endo ([a,b,c]++))
    tell (Endo ([d]++))

这会神奇地将您的 (++) 重新关联到右侧（哇！每次我重新弄清楚它是如何工作的时候都让我大吃一惊）。成本是差异列表的每个观察（即从差异列表到标准列表的转换）是昂贵的（而对于先前选择的裸列表，多个观察的成本不超过一个观察）。如果您只有一个消费者——例如，对 runWriterT 的顶级调用一劳永逸地使列表变平——这渐进地没有问题，但如果您发现自己调用 listen 或 pass经常查看差异列表，你可能不想选择这个。

如果您觉得这些权衡都不合适，那么第三种选择是使用手指树，例如Seq，观察是免费的（与差异列表不同）并且两端的连接是较短参数中的对数时间（与标准列表不同，它在第一个参数中是线性的），但常量是足够高，在许多情况下您可以注意到它。

writer monad 对列表的效率如何？

How efficient is the writer monad for lists?

haskell

linked-list

monads

writer