Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!wuarchive!julius.cs.uiuc.edu!apple!portal!cup.portal.com!pgl
From: pgl@cup.portal.com (Peter G Ludemann)
Newsgroups: comp.lang.prolog
Subject: Re: Arrays in Prolog
Message-ID: <33777@cup.portal.com>
Date: 12 Sep 90 00:39:27 GMT
References: <3629@goanna.cs.rmit.oz.au> <9668@bunny.GTE.COM>
  <ALBERTO.90Aug31144731@yamuna.cs.umd.edu> <9680@bunny.GTE.COM>
  <11289@alice.UUCP>
Organization: The Portal System (TM)
Lines: 14

IBM-Prolog has arrays and "item-lists" (like arrays, except
that the indexes are arbitrary atoms).  They are O(1) for
access and update.  Updates are undone on backtracking.
(There are also "global terms" which provide associative
tables whose changes may be undone by backtracking or not,
at the programmers control).

I have used item-lists to implement a constraint logic programming
version of n-queens: the algorithm is essentially linear on "n"
whereas even the best of the permute-and-test algorithms is exponential
(for n=20, the constraint version took 40 milliseconds and I gave
up waiting for the conventional program after a few minutes).

- Peter Ludemann	prefered e-mail: ludemann@mlpvm1.iinus1.ibm.com