Re: [Caml-list] What is an applicative functor?

[Lucas Dixon <ldixon@inf.ed.ac.uk>]

On 13/04/2011 03:23, Andreas Rossberg wrote:
> On Apr 13, 2011, at 04:36, Lucas Dixon wrote:
>>> I agree with Jacques. My primary argument for applicative functors is
>>> diamond import in libraries. Assume you have a set functor in a
>>> library A
>>> (e.g. the stdlib). Then there are two seperate libraries B and C,
>>> perhaps
>>> from different sources. Both need to use sets. And you want to use B
>>> and C
>>> and pass sets from one to the other.
>>>
>>> Without applicative functors, there are 3 possibilities:
>>>
>>> 1. Both B and C instantiate the Set functor separately and export the
>>> result
>>> -- then you have to convert between the incompatible set types all
>>> the time.
>>>
>>> 2. Both B and C functorize all their modules over a Set instance -- I
>>> think
>>> it's obvious that this doesn't scale.
>>
>> What do you feel is the problem is with scaling this up? (maybe I'm
>> being dumb, but I don't see what the issue is...)
>
> The problem is that you need to turn every module using a functor into a
> functor itself, and eventually end up piling up the entire transitive
> closure of your dependency graph in your functor parameters.

yes, the concept of module for SML is really a functor and dependencies 
are explicit.

> My experience with the early MLKit, which used this so-called "closed
> functor style", was that it is horrible. You need lots of functor
> parameters, lots of structure nesting and reexporting (the sizes of
> signatures can grow exponentially!),  and plenty of subtle sharing
> constraints.

My feeling was that a little improvement on the syntax of signatures and 
sharing would deal with these issues fairly easily.

In terms of growing exponentially: that sounds like a serious problem; I 
would expect it to grow linearly on the number of dependencies. Or did 
you mean to use exponentially informally; as in gets too bug too quick?

> And when some new code you're writing does not type check,
> you sometimes spend considerable time figuring out whether that was a
> "real" error or you just forgot some type sharing somewhere.

I ended up pushing improvements to the type-error printing which helped 
a lot in PolyML. That combined with a finding a style that works out not 
too hideously: I create a sub-structure, typically called "Sharing" to 
hold just types that are relevant to a particular module. I can then use 
sharing on this substructure to share all types and save the others 
painful problem to remember to share every type.

For example, see basic_graph.ML in Quantomatic code (a graph rewriting 
tool in SML):
http://isaplanner.svn.sourceforge.net/viewvc/isaplanner/trunk/quantomatic/core/graph/basic_graph.ML?revision=3017&view=markup

So my basic feeling is still that this is an issue of finding a little 
syntax sugar and then the functorial style could work well... (with the 
sub-structure style I find it bearable, and can even enjoy using functors).

I guess the prerogative is to write that sugar and then try re-tasting 
the functorial soup.

best,
lucas

-- 
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.