作者monad的列表效率如何？

Question

list(Writer [w] a)上的Haskell编写器monad的实现将用于++添加项目.所以,如果我在列表编写器monad中编写此代码:

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

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

我的工作量一次向作者monad添加一条"消息",因此第二个参数++通常是单例列表.

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

Answer 1

左关联(++)s是低效的,因为最左边的列表被遍历多次,每次封闭一次(++).权利相关(++)是好的(至少,通过(:)直接使用它们不能提高效率).

标准WriterT变换器(和(,)编写器)(++)以其绑定相关联的方式关联它们的调用.因此,通过前面的讨论的扩展,左相关的(>>=)s将是有问题的,而右相关的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]++))

这将神奇地将你的(++)s 重新关联到右边(哇!每当我重新弄清楚它是如何工作的时候,我都会想到这一点).成本是差异列表的每次观察(即,从差异列表到标准列表的转换)是昂贵的(而对于先前选择的裸列表,多次观察花费不超过一次观察).如果你只有一个消费者 - 比如说,一个顶级调用就会runWriterT一劳永逸地平整列表 - 这不是渐进式的问题,但如果你发现自己经常打电话listen或pass检查差异列表,你可能不想要选择这个.

如果这些权衡对你来说都不合适,第三种选择就是使用手指树,例如Seq,观察是免费的(与差异列表不同),并且任何一端的连接都是较短参数的对数时间(与标准列表不同) ,它在第一个参数中是线性的,但是对于哪个常数足够高,你可以在很多情况下注意到它.