[Haskell-cafe] Re: Codensity improvement of free monads

On Mon, Jan 25, 2010 at 7:37 PM, Luke Palmer wrote:

...

Hello haskell-cafe,

I have just read "Asymptotic Improvement of Computations over Free Monads" by Janis Voigtlander, since I have been working with free monads a lot recently and don't want to get hit by their quadratic performance when I start to care about that.

But after reading the paper, I still don't really understand how "improve" actually improves anything. Can anyone provide a good explanation for where the work is saved?

Edward gives the perfect explanation below. Thanks, Janis.

With a free monad, the structure keeps growing via substitution. This requires you on each bind to re-traverse the common root of the free monad, which isn't changing in each successive version.

Lets say the size of this accumulated detritus increases by one each time. Then you will be traversing over 1, 2, 3, 4, ... items to get to the values that you are substituting as you keep binding your free monadic computation. The area near the root of your structure keeps getting walked over and over, but there isn't any work do to there, the only thing bind can do is substitution, and all the substitution is down by the leaves.

On the other hand, when you have CPS transformed it, at each layer you only have to climb over the 1 item you just added to get to where you apply the next computation.

This only gets better when you are dealing with free monads that provide multiple points for extension: i.e. that grow in a treelike fashion like:

data Bin a = Bin a a data Free f a = Return a | Free (f (Free f a)) data Codensity f a = Codensity (forall r. (a -> f r) -> f r)

If you build the free monad Free Bin, then you will wind up having to walk all the way down to the leaves on each bind, well, modulo demand, that is. But since it is a free monad, the 'body' of the tree will never change. Just the data you are substituting at the leaves. Codensity (Free Bin) lets you only generate the body of the tree once, while your substitutions just get pushed down to the leaves in one pass.

An interesting exercise is to work out why Codensity can change the asymptotics of certain operations over Free Bin, but Density doesn't change the asymptotics of anything non-trivial over Cofree Bin for the better.

-Edward Kmett

-- Jun.-Prof. Dr. Janis Voigtländer http://www.iai.uni-bonn.de/~jv/ mailto:jv@iai.uni-bonn.de