From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 3C2F9801CD for ; Sat, 19 Aug 2017 11:25:50 +0200 (CEST) X-IronPort-AV: E=Sophos;i="5.41,396,1498514400"; d="scan'208";a="234805375" Received: from aaubervilliers-653-1-164-124.w83-112.abo.wanadoo.fr (HELO pc27.home) ([83.112.79.124]) by mail3-relais-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES128-SHA; 19 Aug 2017 11:25:49 +0200 To: =?UTF-8?Q?Christoph_H=c3=b6ger?= , OCaml Mailing List References: From: =?UTF-8?Q?Fran=c3=a7ois_Pottier?= Message-ID: <947a78df-a8f9-0fa9-1b27-85b807b5af59@inria.fr> Date: Sat, 19 Aug 2017 11:25:52 +0200 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.11; rv:45.0) Gecko/20100101 Thunderbird/45.8.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Subject: Re: [Caml-list] default fold for visitors 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/