From andrew@microspec.co.il Thu Apr 27 09:43:51 2000 Received: from server.microspec.co.il ([192.114.86.34]) by swi.psy.uva.nl (8.9.3/8.9.3) with ESMTP id JAA20368 for ; Thu, 27 Apr 2000 09:43:48 +0200 (MET DST) Received: by SERVER with Internet Mail Service (5.5.2448.0) id ; Thu, 27 Apr 2000 10:43:47 +0300 Message-ID: From: andrew To: "'Fischer'" , "Politini, Cohen" Cc: prolog@swi.psy.uva.nl Subject: RE: UNDERSTANDING LISTS Date: Thu, 27 Apr 2000 10:43:37 +0300 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2448.0) Content-Type: text/plain; charset="windows-1252" 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. 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). In our intuition we apply to middle and last elements of a list, but Prolog limits our access only to the first elements. As the result, you see sophisticated calls of member(...), append(...), concat(...) etc when doing trivial things with sequences of entities (ses below). 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. Access to middle elements of a list was made in Planner, Snobol, Refal, Analitic languages. Sampletalk (see http:\\sampletalk.8m.com) is an attempt to simplify this in Logic Programming style: see examples for word and list processing. Regards Andrew Gleibman -----Original Message----- From: Fischer [mailto:ino-waiting@gmx.net] Sent: Thursday, April 27, 2000 3:35 AM To: Politini, Cohen Cc: prolog@swi.psy.uva.nl Subject: Re: UNDERSTANDING LISTS 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! -- ino-waiting@gmx.net ---------------- * To UNSUBSCRIBE, please use the HTML form at http://www.swi.psy.uva.nl/projects/SWI-Prolog/index.html#mailinglist or send mail to prolog-request@swi.psy.uva.nl using the Subject: "unsubscribe" (without the quotes) and *no* message body. ** An ARCHIVE of this list is maintained at http://www.swi.psy.uva.nl/projects/SWI-Prolog/mailinglist/archive/