Lisp 3 more on lists processing

1 . Common Lisp LISTS J.E. Spragg Mitthögskolan 1997 Mitthögskolan 02/18/19 

2 . Lists  Lists are one of the fundamental data structures in Lisp.  However, it is not the only data structure.  Common Lisp has moved on from being merely a LISt Processor. Mitthögskolan 02/18/19 

3 . Conses  What cons really does is combines two objects into a two-part object called a cons.  Conceptually, a cons is a pair of pointers.  The first one is the car, and the second is the cdr.  Conses provide a convenient representation for pairs of any type.  The two halves of a cons can point to any kind of object, including conses.  This is the mechanism for building lists. Mitthögskolan 02/18/19 

4 . Pairs  Lists in CL are defined as pairs.  Any non empty list can be considered as a pair of the first element and the rest of the list.  We use one half of the cons to point to the first element of the list, and the other to point to the rest of the list (which is either another cons or nil). Mitthögskolan 02/18/19 

5 . Box notation nil a A one element list (A) nil a b c A list of 3 elements (A B C) Mitthögskolan 02/18/19 

6 . What sort of list is this? a d nil b c > (setf z (list ‘a (list ‘b ‘c) ‘d)) (A (B C) D) Mitthögskolan 02/18/19 

7 . Lists of lists  Given z is (A (B C) D)  What value is returned here? – > (car (cdr z)) Mitthögskolan 02/18/19 

8 . Consp  The function consp returns true if its argument is a cons.  So listp could be defined: (defun our-listp (x) (or (null x) (consp x)))  Since everything that is not a cons is an atom, the predicate atom could be defined: (defun out-atom (x) (not (consp x)))  Remember, nil is both an atom and a list. Mitthögskolan 02/18/19 

9 . Equality  Each time you call cons, Lisp allocates a new piece of memory with room for two pointers.  So if we call cons twice with the same arguments, we get back two values that look the same, but are in fact distinct objects: > (eql (cons ‘a nil) (cons ‘a nil)) NIL Mitthögskolan 02/18/19 

10 . Equal  We also need to be able to ask whether two lists have the same elements.  CL provides an equality predicate for this, equal.  eql returns true only if its arguments are the same object,  equal, more or less, returns true if its arguments would print the same. > (equal (cons ‘a nil) (cons ‘a nil)) T  Note: if x and y are eql, they are also equal. Mitthögskolan 02/18/19 1 

11 . Why Lisp has no pointers  One of the secrets to understanding Lisp is to realize that variables have values in the same way that lists have elements.  As conses have pointers to their elements, variables have pointers to their values. Mitthögskolan 02/18/19 1 

12 . Pointers to values  What happens, for example, when we set two variables to the same list: > (setf x ‘(a b c)) (A B C) > (setf y x) (A B C) Mitthögskolan 02/18/19 1 

13 .  The location in memory associated with the variable x does not contain the list itself, but a pointer to it.  When we assign the same value to y, Lisp copies the pointer, not the list.  Therefore, what would the value of > (eql x y) be, T or NIL? Mitthögskolan 02/18/19 1 

14 . Building Lists  The function copy-list takes a list and returns a copy of it.  The new list will have the same elements, but contained in new conses. > (setf x ‘(a b c) y (copy-list x)) (A B C)  Spend a few minutes to draw a box diagram of x and y to show where the pointers point. Mitthögskolan 02/18/19 1 

15 . Append  The Common Lisp function append returns the concatenation of any number of lists: > (append ‘(a b) ‘(c d) ‘(e)) (A B C D E)  Append copies all the arguments except the last. Mitthögskolan 02/18/19 1 

16 . List access functions  To find the element at a given position in a list we call the function nth. > (nth 0 ‘(a b c)) A  and to find the nth cdr, we call nthcdr. > (nthcdr 2 ‘(a b c)) (C)  Both nth and nthcdr are zero indexed. Mitthögskolan 02/18/19 1 

17 . Zerop and Last  The function zerop returns true if its argument is zero. > (zerop 0) T  The function last returns the last cons in a list. > (last ‘(a b c)) (C)  We also have: first, second ... tenth, and  cxr, where x is a string of up to four as or ds. Mitthögskolan 02/18/19 1 

18 . Mapping functions  Common Lisp provides several mapping functions.  Mapcar is the most frequently used.  It takes a function and one or more lists, and returns the result of applying the function to elements taken from each list, until one of the list runs out: Mitthögskolan 02/18/19 1 

19 . > (mapcar #’(lambda (x) (+ x 10)) ‘(1 2 3)) Takes one list (11 12 13) > (mapcar #’list ‘(a b c) Takes two lists ‘(1 2 3 4) ) ((A 1) (B 2) (C 3)) Mitthögskolan 02/18/19 1 

20 . Maplist  The related function maplist takes the same arguments, but calls the function on successive cdrs of the lists: > (maplist #’(lambda (x) x) ‘(a b c)) ((A B C) (B C) (C))  There is also mapcan and mapc. Use the on-line Common Lisp the Language to discover what these mapping functions do. Mitthögskolan 02/18/19 2 

21 . Keyword arguments > (member ‘b ‘(a b c)) (B C)  Member returns true, but instead of simply returning t, its returns the part of the list beginning with the object it was looking for.  By default, member compares objects using eql.  You can override this behavior by employing a keyword argument. Mitthögskolan 02/18/19 2 

22 . Using the keyword argument  An example of a keyword argument is :test.  If we pass some function as the :test argument in a call to member, than that function will be used to test for equality instead of eql. > (member ‘(a) ‘((a) (z)) :test #’equal) ((A) (Z)) Tells to use this function to do equality comparison  Keyword arguments are always optional. Mitthögskolan 02/18/19 2 

23 . Using the key argument  Another keyword argument accepted by member is a :key argument.  This allows you to specify a function to be applied to each element before comparison : > (member ‘a ‘((a b) (c d)) :key #’car) ((A B) (C D)) Mitthögskolan 02/18/19 2 

24 . Member-if  If we want to find an element satisfying an arbitrary predicate we use the function member-if: > (member-if #’oddp ‘(2 4 6 3 7 14)) (3 7 14) First odd number from the left Mitthögskolan 02/18/19 2 

25 . adjoin  The function adjoin is like a conditional cons.  It takes an object and a list, and conses the object onto the list only if it is not already a member: > (adjoin ‘b ‘(a b c)) b already existed (A B C) > (adjoin ‘z ‘(a b c)) (Z A B C) Z did not already existed Mitthögskolan 02/18/19 2 

26 . Sets  CL has the functions, union, intersection, and set- difference for performing set operations on lists.  These functions expect exactly two lists and also the same keyword arguments as member.  Remember, there is no notion of ordering in a set. These functions won’t necessarily preserve the order of the two lists.  Give me an example of a call to union. Show the arguments and the return value. Mitthögskolan 02/18/19 2 

27 . Sort  Common Lisp has a built in function called sort.  It takes a sequence and a comparison function of two arguments, and returns a sequence with the same elements, sorted according to the function: > (sort ‘(0 2 1 3 8) #’>) (8 3 2 1 0)  Sort is destructive!!  What can you do if you don’t want your list modified? Mitthögskolan 02/18/19 2 

28 . Every and Some  The functions every and some take a predicate and one or more sequences.  When given just one sequence, they test whether the elements satisfy the predicate: > (every #’oddp ‘(1 3 5)) Every element was odd T > (some #’evenp ‘(1 2 3)) Some element was even T  If they are given more than one sequence, the predicate must take as many arguments as there are sequences, and arguments are drawn one at a time from all the sequences: > (every #’> ‘(1 3 5) ‘(0 2 4)) T Because 1>0 and 3>2 and 5 > 4 Mitthögskolan 02/18/19 2 

29 . Push and Pop  The representation of lists as conses makes it natural to use them as pushdown stacks.  This is done so often that CL provides two macros for the purpose, push, and pop.  Both are defined in terms of setf. (push obj lst) is the same as (setf lst (cons obj lst)  How can pop (pop lst) be defined? Mitthögskolan 02/18/19 2