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

[Janis Voigtländer]

> 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?

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 at iai.uni-bonn.de