haskell - w ~ [a] 的 Control.Monad.Writer 的复杂度是多少？

Question

假设 tell = Flip mappend 它应该是二次的，但这会使这个 Writer 实例变得毫无用处。如果确实如此，可以采取哪些措施来提高性能？

我正在考虑 Control.Monad.Free.Church 以及 Control.Monad.Co Density 中使用的技巧:应该可以重新关联 mapend 调用，就像 Co密度 重新关联 >>= 一样，但我还没有弄清楚具体是如何关联的。

Answer 1

总结一下:

1. 是的，tell正在阅读 [a]二次复杂度为 Writer 。这可以通过使用 DList 来避免。 (它使用了我正在谈论的 Codensity 类似的技巧)或其他数据类型，其 mappend不是O(n^2) .

2. 除此之外，Writer为每个 >>= 生成 thunk用于建立计算。这是一个问题，因为与第一种情况不同，它无法解决。解决方案是使用 State改为 monad。