What is complexity of Control.Monad.Writer for w ~ [a]?

Question

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?

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.

Answer 1

To sum this up:

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).

2. 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.