From mboxrd@z Thu Jan 1 00:00:00 1970 Received: by margaux.inria.fr, Fri, 7 May 93 15:35:20 +0200 Received: from concorde.inria.fr by margaux.inria.fr, Fri, 7 May 93 12:23:05 +0200 Received: from dmi.ens.fr by concorde.inria.fr; Fri, 7 May 1993 12:23:29 +0200 Received: from arnica.ens.fr by dmi.ens.fr (5.65c8/ULM-1.0) Date: Fri, 7 May 93 12:23:00 +0200 From: cousinea@dmi.ens.fr Message-Id: <9305071023.AA00284@arnica.ens.fr> Received: by NeXT.Mailer (1.87.1) Received: by NeXT Mailer (1.87.1) To: Xavier Leroy Subject: Re: new library modules Cc: caml-list@margaux Sender: weis@margaux This is an answer to Xavier which asked me to give examples of preorders on stored objects. I have recently writen programs for solving puzzles. By "puzzle" I mean one-player games in which you start with a given configuration and try to reach a configuration that has a given property. A puzzle is therefore defined by three values: start : 'a possible_moves: 'a -> 'a list accept: 'a -> bool Searching for a solution amounts to exploring the connex component of "start" in the graph defined by function "possible_moves" and it usually requires to memorize the configurations in order to avoid redundant search. In many puzzles there is a natural equivalence between configurations (for instance symetries or permutations of equivalent objects). Therefore, it is natural (and often necessary for efficiency reasons) to save configurations up to that equivalence. Of course, in order to save and retrieve the configurations efficiently, it is necessary to find an strict order relation compatible with this equivalence and I must admit that, very often, this is obtained by first defining a canonical representation for objects of an equivalent class and then using a total order on the canonical forms. However, even in that case, it may be more informative to save the "real" configurations that have been found and not their canonical form in order to end with a configuration data base that reflects the partial spannning tree that has been built to reach a solution. Therefore, I appreciate having the possibility to use a preorder rather than an order in the archive mechanism. --Guy