🚀 go-pugleaf

In article 92Dec10103127@iron.cs.umass.edu, fawcett@iron.cs.umass.edu (Tom Fawcett) writes:
>
>Michael Covington:
>>    Here's a reasonable substitute for a 15-element array:
>> 
>> 	 f(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o)
>> 
>>    Use 'arg' to access elements by numbered position.
>> 
>>    Limitations:
>>      (1) Intriniscally 1-dimensional (but you can make an array of arrays);
>>      (2) Some maximum number of elements (maybe 256).
>
>
>Greg Sidebottom:
>
>> I would add:
>>  (3) element update is O(size of array) in time and space, which is
>>      much worse than O(log size of array) for trees
>
>I think element access and update (via arg/3) is constant time, at least in
>Quintus Prolog.  The QP library file arrays.pl has such an implementation, and
>states that fetch and access are constant.
>
>> Don't think I am Prolog bashing, Prolog is my favorite language.  But
>> I think if you really need constant time access and update arrays, you
>> should probably use some other language.

Let's get that straight: Prolog _has_ constant time access arrays, they happen
to be called structures, as Michael Covington has pointed out correctly.
(In a typed language, the difference between an array and a structure is that
an array is a collection of items of the same type, while a structure groups
together items of different types. In an untyped language like Prolog there is
no need to make this distinction).

Now 'access' in Prolog means unification, which subsumes 'read' and 'assign once'.

What you don't have in Prolog, neither in arrays nor elsewhere, is destructive
assignment. As a consequence, in a situation where you want a slightly modified
version of an array that you already have (_and_ you don't need to keep the old
version) you have to make a copy where you would otherwise destructively modify
the old array.

Modest advertisement: In SEPIA/ECLiPSe we decided to have no arity limit
on structures precisely because of their potential use as arrays. ---------------------------------------------------------------------------
 Joachim Schimpf                                 Email   joachim@ecrc.de 
 European Computer-Industry Research Centre      Phone   +49 89 92699 111
 Arabellastrasse 17, D-8000 Munich 81, Germany   Fax     +49 89 92699 170