Re: [Caml-list] default fold for visitors

["François Pottier" <francois.pottier@inria.fr>]

Dear Christoph,

> Naturally, the set of free variables forms a monoid, so I can
> comfortably use the reduce variety. But that allocates quite a lot of
> temporary sets, so I had a look into the fold variety.

The "fold" variety is more general than the "reduce" variety, but follows
the same pattern (a bottom-up computation, involving set unions), so I do
not think that using "fold" instead of "reduce" will allow you to allocate
fewer temporary sets.

An alternative approach is to use a mutable set (or a mutable reference to
an immutable set) and perform a linear (say, left-to-right) tree traversal
instead of a bottom-up tree traversal. Then, instead of Set.union, only
Set.add is needed. This can be done using the "iter" variety of visitors.

As noted by Gabriel, it is not clear a priori which of these two 
approaches is
faster. This depends on your data and on the data structure with which you
implement sets.

Concerning the implementation of visitors that traverse abstract syntax with
binding, let me mention my upcoming ICFP paper:

   http://gallium.inria.fr/~fpottier/publis/fpottier-visitors-unchained.pdf

and the accompanying library, alphaLib (as yet unreleased / undocumented):

   https://gitlab.inria.fr/fpottier/alphaLib

You may be particularly interested in the implementation of the computation
of the free variables of a term:

   https://gitlab.inria.fr/fpottier/alphaLib/blob/master/src/KitFa.ml
 
https://gitlab.inria.fr/fpottier/alphaLib/blob/master/src/AlphaLibMacros.cppo.ml

> If I understand the documentation correctly, this class requires to
> define a build method for each variant of the datatype. I wonder if
> there is a way to have a "default" function

At the moment, the "fold" variety requires a linear number of "build_"
methods to be written by hand. If you wish to avoid this, then you have
to use a more specific variety, such as "iter", "map", "reduce", etc.

I am aware that the varieties that exist at the moment are somewhat
arbitrary and do not cover every possible wish, but I am deliberately
trying to avoid an explosion in the number of varieties, which I am
afraid would make the package more difficult to maintain.

--
François Pottier
francois.pottier@inria.fr
http://gallium.inria.fr/~fpottier/