24 1024x768

The basie flmciiotw for acccssin# ihc componontś of lisi* aro car and cdr. car lata a single argument, which nuist be a lisi, and returnu the fint element of tltat liii. cdr olio takes a single argument, which musi be a lisi. and return* that list willi its fint argument removcd. For example:

: notę that the list la guofj : the first element of a list mny be a Im

>    (car ’(• b c)) a

>    (cdr'(a be))

(be)

»(car'((ab) (cd)))

(ab)

>    (cdr'((ab) (cd)))

((cd))

>    (car (cdr '(a b c d))) b

The way in which car and cdr operate suggesw a recureivc approaeh to mnnipulatlng list structurcs. To perform an operat ion on eaclt of lite element* of a list:

1.    If the list U cmpiy. quit.

2.    Otherwise. operate on the element and recurac on the remainder of the list.

Using this schemc. we can define a number of uscful list-handling Ameliom. For cxamplc. tom mon LISP includes the predicatcs mombor. which determines whcthcronc s-cxpreNsion is a member of a list. and longth. which determines the length ofalM.lt define our own vcnion« of thesc Ametions: my-member takes two argument*, aa atbi-trary s-cxpression and a list. my-list. It return* nil if the s-cxpression i* nota member of the my-list otherwise it return* the lisa containing the s-ecprcaakm as Hs fint element:

: element not in Hst ; olomont found ; r©cursive step

(dofun my-member (element my Hat)

(cond ((nuli my-list) nil)

((equal element (car my-list)) my-list)

(t (my-member element (cdr my-list)))))

my-mombor ha* the bchavior.

>    (my-member 4 fi 2 3 4 5 6)) (4 5 6)

>    (my member 5 *(a b c d)) nl

Similarły. we nay define our own ver*»on* or longth and nth:

(defun my-length (my łat)

(cond ((nuli my-Ust) 0)

(I (♦ (my length (cdr my list)) 1))))

PART VI / LANOUAGES FOR Al PROBLEM 80LVING

(dofun my-nth (n my-!isl)

(cond ((zerop n) (car my-list))    ; zerop t*sts d rts argument is zero

(I (my-nth (- n 1) (cdr my-Bst)))))

ll is interesting to notc that these cxamplcs. though pcrscnted herc to ifatnte the mc of ca r and cdr. rcflect the historical dcvclopment ofLISP. EarJy vc»ions of the łanjuagc did not include as many built-in functions as Common LISP docs. programnm defined sheir own functions for chccking list membership, length. etę. Oter time, the most getterally use/bl of these functions havc bcen incorporaicd imo the bnguage standard As £> casily cxtcnsible Ianguagc. Common USP mokes it easy for programoiers lo create and nc their own library of reusable functions.

In addition to the functions car and cdr, USP provides a number of fanctiou for ccostmeting lists. One of these. list which takes as argument* any number of s-ctprcssions. evaluates them. and returns a list of the rcsults, was introduced in Scciion 15.1.1. A morę primitive list constructor is the function cons. that takes iwo s-espressions as arguments, evaluatcs them. and retums a list whose car is the \aluc of the fint argument and whose cdr is the valuc of the sccond:

>    (cons 1 '(2 34))

(1234)

>    (cons ’(a b) '(c d e))

((ab)cdo)

cons bcars an invcrsc rclationship to car and cdr in that the car of the va!ue retumed by a cons form is always ihc first argument to the cons, and the cdr of the talue retumed by a cons form is always the sccond argument to that form:

>    (car (cons 1 '(2 34)))

1

>    (cdr (cons 1 ‘(2 3 4)))

(234)

An cxamp!e of the usc of cons is scen in the defimboo of the functim filter-negatives. which takes a list of numbers as an argument and retums that list »*h *y negativc numbers rcmovcd. flllor-negatives rccur$ively examines each element of the list; if the first element is ncgative. it is discarded and the function retums the rcsult of fillering the ncgaiive numbers from the cdr of the IbŁ lf the fint demem of the bt ts pasane. it is “cohscd” onlo Ihc rcsult of filtering negathes from tberefloftbebt

(dofun filter-negativos (number-list)

(cond ((miii number-Ust) nil)    : terrotaaSon eondten

((plusp (car number-Bst)) (cons (car number-fist)

(fllter-negathos (cdr number-Bst)}))

(t (filter-negatlves (cdr numboMist)))))

^his function bchavcs:

693

CHAPTER15/AM WTROOUCTION TO USP