haskell - 列表的 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 转换器(和 (,) writer)将它们的调用关联到 (++)，就像它们的绑定(bind)一样联系。因此，通过前面讨论的延伸，左关联的 (>>=) 将会有问题，而右关联的则没问题。特别是，这意味着存在抽象成本。如果在重构中提取下面 do block 的前两行:

x = do
    tell a
    tell b
    tell c

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

y = do
    tell a
    tell b

x = do
    y
    tell c

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

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

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

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

如果这些权衡对您来说都不好，第三种选择是使用指状树，例如Seq，其中观察是免费的(与差异列表不同)，并且两端的串联在较短的参数中是对数时间(与标准列表不同，在第一个参数中它是线性的)，但是对于常数足够高，在很多情况下您都可以注意到它。