Subject: RE: UNDERSTANDING LISTS

From: "Richard A. O'Keefe" <[email-masked]>
Date: Fri, 28 Apr 2000 13:36:14 +1200 (NZST)

I think Prolog lists is not too intuitive logic model of a
	sequence of entities - they probably resulted as an attempt
	to incorporate something similar to arrays in logic. 
	
WRONG.

Prolog lists are identical to lists in (pure) Lisp, ML, Haskell, Clean,
Hope, NPL, lots of other things.  Lists of this kind are the standard
way to represent sequences in declarative languages.

In particular, they are *not* intended to resemble arrays.

A sequence is either
 - empty, in which case there is nothing else to know
 - or non-empty, in which case it has a first element and
   a sequence of remaining elements.

Turn that into a DEC-10 Prolog type definition:
 :- type list(T) --> empty | non_empty(T, list(T)).
Now you have Prolog lists, except for the spelling of the functors.

Simple, declarative, about as far from arrays as you can imagine.
It is the simplest possible data type that can do the job.

Come to think of it, if you look up "linked list" in a Pascal
data structures book, you'll be told about

    type
	ListElt = Char;       (* or whatever you want *)
        ListPtr = ^ListRec;
        ListRec = record Tail: ListPtr; Head: ListElt end;

    function Cons(Head: ListElt; Tail: ListPtr): ListPtr;
        var Result: ListPtr;
    begin
	new(Result);
	Result^.Tail := Tail;
	Result^.Head := Head;
	Cons := Result;
    end;

which is precisely (a mutable version of) Prolog/ML/Lisp lists.

	The bad thing is that, on the high level, there is no essential 
	difference between a list and a stack (although stacks keep
	only plain numbers).

Yes there is.  To start with, stacks have nothing to do with numbers.
More importantly, "stack" is an ABSTRACT data type providing operations
"make empty stack, is empty stack?, push, pop".  But "list" is a
CONCRETE data type.

	In our intuition we apply to middle and 
	last elements of a list, but Prolog limits our access only to 
	the first elements.

Well, intuitions vary.  [] hasn't any middle or last element.
Prolog does NOT limit your access to only the first element.
It only provides _direct_ access to the head and tail, but precisely
the same is true of standard linked lists in Ada, C, C++, Pascal, ...

	last([H|T], X) :- last_(T, X, H).
	last_([], X, X).
	last_([H|T], X, _) :- last_(T, X, H).

I don't know what is the middle element of a even-length list.

	As the result, you see sophisticated calls of 
	member(...), append(...), concat(...) etc when doing trivial 
	things with sequences of entities (ses below).
	
Just as you would in Pascal or Lisp or Haskell or Clean or ...

	Imagine that you have to use stacks instead of arrays in C or 
	Pascal: you still can work with sequences of things, but your 
	access to middle elements will be painful.
	
Lists are not and were never intended to be a substitute for arrays.
If you want a substitute for arrays, use a 3+4 tree.

	Access to middle elements of a list was made in Planner, 
	Snobol,

It's a long time since I read the Planner manual, but Planner used
Lisp syntax.  I know SNOBOL fairly well, and it DOESN'T provide access
to middle elements of a list.  SNOBOL has arrays.  It also lets you
define standard linked lists, but does NOT offer you any special
access to middle elements.

We were promised an example of "sophisticated calls ... when doing
trivial things".

	 As the result, you see sophisticated calls of 
	member(...), append(...), concat(...) etc when doing trivial 
	things with sequences of entities (ses below).
	
The example never materialised.
And it never materialised for a very simple reason.
It is *easy* to do trivial things with lists in Prolog.
Not many things can be done with simple pattern matches,
but that's true of any data structure.