[Haskell-cafe] Codensity improvement of free monads

[Edward Kmett]

On Mon, Jan 25, 2010 at 7:37 PM, Luke Palmer <lrpalmer at gmail.com> 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?
>

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

Luke
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100125/3be84f5d/attachment.html