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