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)
(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))
> (apply #'car ’((abc)))
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