假设 tell = Flip mappend
它应该是二次的,但这会使这个 Writer
实例变得毫无用处。如果确实如此,可以采取哪些措施来提高性能?
我正在考虑 Control.Monad.Free.Church
以及 Control.Monad.Co Density
中使用的技巧:应该可以重新关联 mapend
调用,就像 Co密度
重新关联 >>=
一样,但我还没有弄清楚具体是如何关联的。
最佳答案
总结一下:
是的,
tell
正在阅读[a]
二次复杂度为Writer
。这可以通过使用DList
来避免。 (它使用了我正在谈论的Codensity
类似的技巧)或其他数据类型,其mappend
不是O(n^2)
.除此之外,
Writer
为每个>>=
生成 thunk用于建立计算。这是一个问题,因为与第一种情况不同,它无法解决。解决方案是使用State
改为 monad。
关于haskell - w ~ [a] 的 Control.Monad.Writer 的复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39368619/