Date: Fri, 7 May 93 12:23:00 +0200
From: cousinea@dmi.ens.fr
Message-Id: <9305071023.AA00284@arnica.ens.fr>
To: Xavier Leroy <xavier@Theory.Stanford.EDU>
Subject: Re: new library modules
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