From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 469F0BC88 for ; Tue, 8 Feb 2005 12:11:26 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j18BBPQL027655 for ; Tue, 8 Feb 2005 12:11:26 +0100 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id MAA17842 for ; Tue, 8 Feb 2005 12:11:25 +0100 (MET) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j18BBPXD027652 for ; Tue, 8 Feb 2005 12:11:25 +0100 Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.11/jtpda-5.4) with ESMTP id j18BBPg8007812 for ; Tue, 8 Feb 2005 12:11:25 +0100 (CET) X-Ids: 164 Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id MAA11968 for ; Tue, 8 Feb 2005 12:08:34 +0100 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id MAA782520 for ; Tue, 8 Feb 2005 12:10:04 +0100 X-Authentication-Warning: ibm1.cicrp.jussieu.fr: fernande owned process doing -bs Date: Tue, 8 Feb 2005 12:10:03 +0100 (NFT) From: Diego Olivier Fernandez Pons X-X-Sender: fernande@ibm1 To: caml-list@inria.fr Subject: Do I need an array of untyped pointers ? Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-1.7.2 (shiva.jussieu.fr [134.157.0.164]); Tue, 08 Feb 2005 12:11:25 +0100 (CET) X-Miltered: at concorde with ID 42089E5D.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 42089E5D.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 42089E5D.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Spam: no; 0.00; pons:01 pons:01 untyped:01 pointers:01 backtracking:01 enumeration:01 recursive:01 backtracking:01 haskell:01 unspecified:01 brisset:01 barnier:01 enumeration:01 rec:01 stack:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: Bonjour, I have a backtracking program that uses data structure persistence to keep track of all alive branches of the enumeration tree f : 'a set -> 'a set -> 'a is a recursive function f a b --> f (add x a) b --> ... --> f a (add x b) --> ... There is an example for the subsetsum problem in comp.lang.functional (Backtracking in Haskell ?) http://groups.google.fr/groups?hl=fr&lr=&selm=6443cc98.0407190449.58f31cc8%40posting.google.com The backtracking is done as usual raising an exception and recovering the previous state (here is where data persistence is useful) I want to expand my program in order to accept an unspecified number of arguments of heterogeneous types [in other words I want a 'generic' function f in the sense that you do not have to write it again for every specific problem] There are two problems : - variable number of arguments - arguments of different type (set, map, ...) There is a well known trick (used e.g in FaCiLe by Pascal Brisset and Nicolas Barnier) which consists basically on making all operations have the same 'type' (unit -> unit) and saving them all in a persistent data structure (list type) Then you have a 'single' data structure and you do/undo modifications when you go up/down the enumeration tree. (from FaCiLe 1.1 fcl_stak.ml) let backtrack_all () = let rec bt = function Level {failure=s} -> bt s | Empty -> reset () | Trail (undo, s) -> undo (); bt s in bt !stack The problem is that I don't see the point in letting the garbage collector sweep the 'previous' data structure and build it back some time after when you only had to hold it (keeping it alive with a pointer). I went to the conclusion that what I seemed to need was a kind of 'untyped array of pointers' which is in a sense what the compiler uses when one writes f a b c d ... Any suggestion on how to workaround ? Diego Olivier