32 1024x768

ISJ.I Mops and Filters

A >/fcr i% a funcUoo thai applics a test to ihc element* of a lisi. climinating thosc (hal fail che tesi filfor-negativos. proented carlicr in Uiis chaptcr. \vas an cxampłc of a filier. Mapt lako a lisi of data objects and apply u function lo cach one. retuming a lisi of ihc rcsulis. This idea may be funher generał i/cd ihrough ihc dcvclopmcni of generał mapt and filicrs fiut lakę as argumenis both lisis and ihc functions or tesli; llini arc lo be applied lo ihcir elements.

To begin u ich an cxamplc. recall ihc Ainction fillor-negatives from Section 15.1.6, This funciion Urok as iis argument a lisi of numbers and returned Ihal lisi wiih all negaińc \alucs dclcied. Similarly. a funciion lo filier out all ihc cvcn numbers in a lisi may be defined:

(delun filtor*evens (numbor-list)    ; lerminalion oondWon

(cond ((nuli numbor-llst) nU)

((oddp (car numbor-llst))

(eona (car numbor-list) (filtor-ovons (cdr number-lisl))))

(I (filter-ovons (cdr number-list)))))

Bccausc ihesc two functions difler onły in ihc namc of Ihc prcdicalc uscd lo filier elements from the list. ii is naturaI lo think of generalizing them into a single funciion thai lak es ihc fillcring prcdicalc as a sccond paramcler.

This may be defined using u LISP form called funcall. which lakcs as argumcnls « funciion and a senes of argumcnls and applics thai function 10 lhosc argumenis:

(dofun filier (list-of olomonts test)

(cond ((nuli list-of elements) nil)

((funcal test (car list-of-elements))

(eona (car list-of-elements) (filtor (cdr list-of-elemonts) test)))

(I (filter (cdr list-of eloments) test))))

The function. filier, applics the test to the first element of the list. If the test return non-nil. it conscs the element onto the result of fillcring the cdr of the list: othcrwi&c. ii just rciurns the filtered cdr. This function may be uscd with diITcrciit prcdicales passed in as param et ers to perform a yariety of filtering tasks:

; Filter out all negattoe numbars ; Filter out all odd numbers ; Filter out al! non-numbers

>    (filter ‘(1 3-9 5-2 -7 6) rplusp)

(1356)

>    (filter '(123456789) revenp)

(2468)

>    (filter ’(1 a b 3 c 4 7 d) #'numborp)

(134 7)

When a function is passed as a parameter, as in the above cxamplcs. it should be pre-ccded by a #* instead of just \ The purpose of this convcntion is to flag argumenis thai arc functions so thai they may be givcn appropriate treatmem by the LISP interpreter. In psi-ticular. when a function is passed as an argument in Common LISP. the bindings of its fice

PART VI / LANGUAGES FOR Al PROBLEM SOLVINO

tóriablcs (if nny) must bc rctaincd. This combination of functioo dcfinltion and btodmg* of free \:mablcs is callcd a lcxlcal dosunr. the f informs LISP thai the lesieal cłMure niu>: be constructcd and passed with Ihc function. Morc focnolły. funcall is defined:

(funcall <funotion> <arg,> <arg,>... <arg.>)

la this definition. <function> is a LISP function and <arg,>... <arg,> are /ero or morc HgumenU lo the funciion. The resuh of csihating a funcall is Ac same at the rcsult of crcluaiing <funcUon> with the spccificd argumenis as actual panaeten.

apply is a similar function thai perfotms the same task as funcall but rc^uites that its argumenis bc in a list. Exccpt for this syntactic diffcrcnce, appły and funcal bebwt the ramę; the programmer can choose the function that sccirn morę cometueol for a gis en jępłication. These two functions are similar to 0val in that all thrcc of them alkm the oscr d specify thai function evaluation should tako place. The diffcrencc is thai eval rcquircs to argument to be an s-cxprcssion that U cvaluatcd: funcall and appły take a function and to arguments as separate parninclcrs. I- \amplcs of the behrór of ibesc functions are:

>    (funcall #‘plus 2 3)

5

>    (appły rpka *(23))

8

I> (oval '(plus 2 3))

> (funcall #’car '(a b c))

a

> (apply #'car ’((abc)))

a

Anothcr imponant cłass of higher-order functions consists of mapping functions, fonctions that will apply a givcn funciion to all the elcmcnu of a list. Using funcall, we define the simplc mapping function map-simple. which retums a list of the rcsults of appłying a functional to all the elements of a list. It bas the bcłuiion

(dofun map-simple (func list)

(cond ((nuli list) nil)

(t (cons (funcall func (car Ust))

(map-simple func (cdr list))))))

> (map-simple fi* '(12 3 4 5 6))

(234 56 7)

> (map-simple Wistp '(1 2 (3 4) 5 (6 7 8)))

(nl nl t nl t)

map-simple is a simplifted vcrsion of a USP buili-in function mapcar. that iik*s ■ore than one argument list. so that functions of moce tłnn ooe argument can bc applKd tocorresponding elements of scvcral lists:

> (mapcar #1+'(1 23456))    ;W» to tha samo as map-simple

(234567)

709

CHARTER 15/M tłTROOUCTlOHTOUSP