🚀 go-pugleaf

> 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