w〜[a]的Control.Monad.Writer的复杂度是多少?

问题描述

假设tell = flip mappend应该是二次的，但这会使该Writer实例变得毫无用处.如果真的是这样，可以采取什么措施来提高性能?

Assuming tell = flip mappend it should be quadratic, but that would make this Writer instance pretty useless. If it's really so, what can be done to improve performance?

我正在考虑Control.Monad.Free.Church和Control.Monad.Codensity中使用的技巧:应该可以重新关联mappend调用，就像Codensity重新关联>>=一样，但是我没有想到完全正确.

I'm thinking of trick that was used in Control.Monad.Free.Church as well as Control.Monad.Codensity: it should be possible to reassociate mappend calls, just like Codensity reassociates >>=, but i haven't figured how exactly.

推荐答案

总结一下:

1. 是的，tell中的tell在Writer中具有二次复杂度.可以通过使用DList(它使用我刚才说过的类似Codensity的技巧)或其他mappend不是O(n^2)的数据类型来避免.

1. Yes, telling an [a] has quadratic complexity in Writer. This can be avoided by using DList (which uses that Codensity-like trick I was talking about) or another datatype whose mappend isn't O(n^2).

最重要的是，Writer为用于构建计算的每个>>=生成thunk.这是一个问题，因为与第一种情况不同，它无法解决.解决方案是改用State monad.

On top of that, Writer generates thunks for each >>= used to build up a computation. This is a problem because unlike the first case it can't be worked around. The solution is to use State monad instead.

这篇关于w〜[a]的Control.Monad.Writer的复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！