Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!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: <34487@cup.portal.com>
Date: 3 Oct 90 02:47:45 GMT
References: <1238@ecrc.de> <1990Sep19.075314.14372@irisa.fr> <1403@ecrc.de>
Organization: The Portal System (TM)
Lines: 28

> I would like to point out that there is no such thing as
> "(virtual) modification in O(1) without destructive assignment".
> Basically, your modifiable data structure is still a list, where
> the current value is stored at the end, together with a free place
> for adding further modifications. 
> A change history will therefore look like this (using infix dots): 
>  
> X = value1 . T1
> X = value1 . value2 . T2			Trail: T1
> X = value1 . value2 . value3 . T3		Trail: T2, T1
> X = value1 . value2 . value3 . value4 . T4	Trail: T3, T2, T1

Eh?  All you need to store for each entry in the trail is:
	(pointer to array, index, old value)
and you're back to O(1). 

You'll speed things up by a constant factor if you can figure
when the values don't need to be trailed.

Can we change the subject a bit?  How about list structures
which can be as easily accessed from the end as from the front?
That, to me, is the big advantage of arrays; not the performance
improvement.  Does anyone have a nice notation for getting the
last element of a list as opposed to the first element?
Maybe something like Icon, where a[1] gets the first element and
a[-1] gets the last element.

- Peter Ludemann	ludemann@mlpvm1.iinus1.ibm.com