🚀 go-pugleaf

In article <9680@bunny.GTE.COM> tomf@GTE.COM (Tom Fawcett) writes:
>alberto@cs.umd.edu (Jose Alberto Fernandez R) writes:
>> 	[Long message suggesting a way to represent a board sequence
>>		without using arrays]
> I'm
>doing a search through successor boards, trying to find the best next move
>(like a minimax search, but not really).  I may end up having to search
>several ply.  In this case, your scheme doesn't work because the boards aren't
>in a linear sequence.
A multiversion data structure, such as the flexible arrays mentioned earlier
by Richard O'Keefe, will almost certainly be much faster for this application,
as well as much cleaner logically, than database modification. Ideally, of
course, Prolog systems should provide efficient implementations of
multiversion aggregate data structures (arrays, hash tables) 
with O(1) access time and update to the elements of some versions (eg.
the most recent one). Such schemes have been described in the
literature, and discussions like this one indicate that they are badly
needed in Prolog (in in pure functional languages as well!).

Multiversion graph data structures are also very important in applications
such as CAD, heuristic compiler optimizations, in which complex descriptions
must be tentatively changed to examine alternative courses of action.
For DAGs with fixed in-degree, there are very nice multiversion
representations due to Tarjan et al (can't find the exact reference
right now).

Fernando Pereira
2D-447, AT&T Bell Laboratories
600 Mountain Ave, Murray Hill, NJ 07974
pereira@research.att.com