Path: utzoo!utgpu!watserv1!watmath!att!dptg!ulysses!andante!alice!pereira From: pereira@alice.UUCP (Fernando Pereira) Newsgroups: comp.lang.prolog Subject: Re: Arrays in Prolog Message-ID: <11289@alice.UUCP> Date: 5 Sep 90 02:32:47 GMT References: <3629@goanna.cs.rmit.oz.au> <9668@bunny.GTE.COM> <9680@bunny.GTE.COM> Reply-To: pereira@alice.UUCP () Organization: AT&T, Bell Labs Lines: 34 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