Subject: Re: UNDERSTANDING LISTS

From: Fischer <[email-masked]>
Date: Thu, 27 Apr 2000 04:35:01 +0200 (CEST)

On Thu, 27 Apr 2000, Politini, Cohen wrote:

> I seem to find it very hard to comprehend LISTS. Can you please give me a

lists are an abstraction of a collection of different objects.  you might
think of a list as a stack of plates.  you can get easily at the topmost
plate, but with two hands, the others are just the rest of them.

some abstraction for storing compound data is needed, and lists can be used
to do anything.  something with one single up front and then comes the rest
can be implemented using an indirect numbering scheme.  the list can be
represented giving the number of the storage cell where it starts.  then
where the first object ends a second number gives the storage cell of where
the rest of the list, called the tail, can be found.  this principle can be
used to store objects of different storage requirements and it is repeated
until the end of the list is reached.  said numbers are called pointers and
the structure is a linked-list with each element pointing to the next, the
last element usually having a NULL pointer to indicate that nothing
follows.

the programmer creates a set of predicates to handle lists so as not to be
confined to prologs basic list constructor, but [Head | Tail] is all you
get, none the less.  take the member function:  it's a description for the
situation where something can be unified with that topmost element, the head.
but since that something is not neccessarily right the first object in the
list, the constructor/deconstructor has to be applied by member/2 successively
until it is.

member(_H, []) :- fail. % no list, no membership

member(H, [H|_Tail]). % this is apparently true for the semantics of member/2
                      % first element of the list unifies with the argument

member(H, [_H1, H |_Tail]). % not the first, but maybe the second?
member(H, [_H1, _H2, H |_Tail]). % ok, might be the third.
member(H, [_H1, _H2, _H3, H |_Tail]). % or the fourth?

% these are all valid prolog statements.  you can use them for lists of up
% to four header checks deep, i.e. the predicate as given will work if the
% element we're after is one of the first four.

% now lists can be any length.  we have to optimize.  the first rule says
% what's NOT the case.  prolog delivers false in case nothing appropriate is
% defined, so we just leave out the first rule:  empty lists are not
% considered.
% now if we could devise a scheme or generalisation for the other rules
% given, which could lead us to lists of arbitrary length...  lets look at
% them.  the test is performed for the accessible element of the list with
% the preceeding elements taken off.  how is an element taken off?  with the
% list constructor/deconstructor.  and what's our test-case?  equality of
% argument and list-head.

member(H, List) :-             % the general case:
	List = [_Head | Tail], % take first off,
	member(H, Tail).       % ...and check the rest.

% everything considered and put into one definition, member can be written
% like it appears in every book:

member(H, [H|_Tail]). % this is apparently true for the semantics of member/2
member(H, [_SomeHead|Tail]) :- % if it's not the head, try the tail
	member(H, Tail).

i should mention that variables beginning with an underscore might just as
well be shortened to '_' , because they are anonymous, they aren't used.
this taken into account leaves us with:

member(H, [H|_]).       % this is apparently true for the semantics of member/2
member(H, [_|Tail]) :-  % if it's not the head, try the tail
	member(H, Tail).

did y'all sleep well?  tomorrow i might be tempted to try myself on
appending two lists to form the concatenated result, so don't make me
angry.  i'd rather you'd criticize how i did, and class:  you may address
questions at me!

-- 
[email-masked]