Apelul funcţiilor. Iteraţia. Lambda.
Primitivele MAPCAR şi APPLY
Un mod câteodeta mai elegant de a realiza iteraţiile este de
a folosi primitivele MAPCAR şi APPLY.
MAPCAR se foloseşte
atunci când dorim să aplicăm o procedură la fiecare element
al unei liste. MAPCAR va returna lista rezultatelor.
Sintaxa:
(mapcar <nume procedura>
<lista
de argumente>)
| MAPCAR |
|
(mapcar 'oddp'(1 2 3))
(t nil t)
|
Aici MAPCAR produce execuţia iterativă
a predicatului oddp pe fiecare element al
listei. Rezultatele sunt colectate într-o lista.
APPLY aplică o procedură
unei liste de argumente (nu fiecaruia în parte cum face MAPCAR).
Sintaxa:
(apply <nume procedura>
<lista
argumente>)
| APPLY |
|
Dacă avem o listă de numere
(setq l '(4 7 2))
şi dorim să adunăm numerele din lista, ar fi greşit să evaluăm
(+ l)
pentru ca + aşteptă argumente care sunt numere dar aici primeşte
o listă de numere. De fapt am încercat să evaluăm mai sus
(+ '(4 7 2))
ceea ce evidend e greşit. Ceea ce am dori ar fi
(+ 4 7 2)
Tocmai acest lucru îl face APPLY
(apply '+ l)
13 |
Folosind MAPCAR şi APPLY împreuna putem rezolva mult mai elegant
probleme complex recursive.
| COUNT-ATOMS |
| O implementare mai eficientă a procedurii COUNT-ATOMS
(numară atomii dintr-o listă generalizată):
(defun count-atoms (l)
(cond ((null l) 0)
((atom
l) 1)
(t
(apply '+
(mapcar
'count-atoms l)
)))))
Aici recursivitatea nu se face doar pe două
direcţii odată (car şi cdr, adică primul fiu
şi frate drept), ci pe toţi fii simultan. Se face astfel
o parcugere in lăţime a arborelui generalizat.
|
| DEPTH |
| Următoarea procedură returnează
adâncimea unui arbore generalizat.
(defun depth (l)
(cond ((null l) 1)
((atom l)
0)
(t (+ 1
(apply 'max (mapcar 'depth l)))))) |
MAPCAN
Primitiva MAPCAN se comportă ca şi
MAPCAR combinat cu APPEND.
Sintaxa:
(MAPCAN <nume procedura> <lista argumente>))
==
== (APPLY 'APPEND (MAPCAR <nume procedura> <lista argumente>))
Iteraţii folosind DO
Instrucţiunea DO putem folosii asemanator ca intrucţiunule for şi do/while
din limbajele de programare cunoscute
Sintaxa:
(DO ((<param 1> <valoare initala 1>
<actualizare 1>)
(<param 2> <valoare initala 2>
<actualizare 2>)
...
(<param n> <valoare initala n>
<actualizare n>))
(<test sfarsit> <rezultat>)
(<corpul lui do>))
DO face şi legarea parametrilor.
| Ridicare la putere întreagă |
|
(defun expt (m n)
(do ((result 1) ;
legare şi atribuire result
(exponent n))
;
legare şi atr. exponent
((zerop exponent)
result) ; test şi return
(setq result (*
m result)) ; corp
(setq exponent
(- exponent 1)))) ; corp
sau folosind câmpul de actualizare a variabilelor:
(defun expt (m n)
(do ((result 1 (* m result)) ;
legare, iniţializare, actualizare
(exponent
n (- exponent 1))) ; legare, iniţializare,
actualizare
((zerop exponent)
result)
)) ;
corp gol
|
| Problema 1 |
|
Implementaţi urmatoarele operaţii cu mulţimi:
reuniune, intersecţie, diferenţă, test de egalitate. |
| Problema 2 |
| Implementaţi un program LISP care primeşte
o expresie logică pe care o transformă, folosind legile
lui de Morgan, într-o expresie logică folosind doar operatorul
NAND.
Observaţie: Souluţia nu trebuie să
fie optimizată. Exemple:
(DEMORG '(and a (not b)))
(NAND (NAND A (NAND B B) ) TRUE)
(DEMORG '(or a b c)))
(NAND (NAND A A) (NAND B B) (NAND C C))
(DEMORG '(and a (or c d) (not e)))
(NAND (NAND A (NAND (NAND C C) (NAND D D)) (NAND E E)) (NAND A (NAND (NAND C C) (NAND D D)) (NAND E E)))
|
LAMBDA
LAMBDA defineşte proceduri anonime.
| LAMBDA |
|
Să presupunem că avem o listă de numere şi div3 este o procedură care verifică dacă un număr este divizibil cu trei.
(setq numbers '(4 6 3 8 9 7))
(4 6 3 8 9 7)
(defun div3 (x)
(zerop (rem x 3)))
Folosind mapcar cu procedura div3 putem verifica elementele din lista care sunt divizibile cu trei:
(mapcar 'div3 numbers)
(nil t t nil t nil)
Dacă funcţia div3 nu o mai folosim în altă parte, putem să o definim chiar
în locul în care apare (mapcar poate primi nu numai numele unei
funcţii ci chiar definiţia ei):
(mapcar (defun div3 (x)
(zerop
(rem x 3)))
numbers)
(nil t t nil t nil)
De fapt mapcar primeşte
tot numele unei proceduri, pentru că defun după ce defineşte
procedura returnează numele ei (vezi lucrarea
3). Observăm că numele procedurii div3
nu mai este util dacă procedura apare doar în acest loc.
Ar fi util, pentru a evita proliferarea numelor inutile, ca procedura
care verifică dacă un număr este divizibil cu trei să nu aibă
nume (să fie anonimă). Acest lucru îl specificam printr-o primitivă
asemanatoare cu defun, numită din motive istorice lambda. Deci
pentru a folosi o definiţie locală anonimă scriem:
(mapcar '(lambda (x)
(zerop
(rem x 3)))
numbers)
(nil t t nil t nil)
|
Primitiva lambda seamană foarte mult cu defun, doar că nu dă nume
procedurii definite, putând fi folosită astfel doar în definiţii locale.
Observaţi că primitiva lambda poate să apară practic oriunde apare
numele unei funcţii. În particular poate să apară pe prima poziţie
a unei forme care va fi evaluată. Următoarele expresii sunt echivalente,
presupunând definit div3:
(div3 6)
((lambda (x) (zerop (rem x 3))) 6)
| COUNT-DIV3 |
| Urmariţi următorul exemplu în care
definim o procedură care numară câte elemente dintr-o
listă sunt divizibile cu trei:
(defun count-div3 (l)
(apply '+ (mapcar
'(lambda
(x)
(cond
((zerop (rem x 3)) 1)
(t
0)))
l)))
COUNT-DIV3
(count-div3 numbers)
3
|
Predicatul REMOVE-IF-NOT
Predicatul remove-if-not este asemănător cu mapcar dar pastrează în
rezultatul final doar elementele pentru care un anumit predicat este adevărat.
| REMOVE-IF-NOT |
|
(remove-if-not 'div3 numbers)
(6 3 9)
Şi aici putem folosi lambda:
(remove-if-not '(lambda (x)
(zerop
(rem x 3)))
numbers)
(6 3 9)
|
Lambda interfaţează proceduri la liste de argumente.
| COUNT-DEEP-DIV3 |
|
Considerăm o listă generalizată în care dorim
să numărăm elementele divizibile cu un număr dat::
(defun count-deep-div (n l)
(cond ((atom l) (cond ((zerop
(rem l n)) 1)
(t
0)))
(t
(apply '+
(mapcar
'(lambda (e) (count-deep-div n e))
l)))))
Nu puteam aplica recursiv direct (mapcar 'count-deep-div3
l) pentru ca procedura count-deep-div3 are nevoie de doi parametrii
iar mapcar îi furnizează doar câte unul. Aici lambda reailzează
interfaţarea dorită a procedurii.
|
| Problema 3 |
| Realizaţi, folosind mapcar
şi lambda, o procedură count-atom
care determină numărul de apariţii a unui atom într-o
listă generalizată.
(count-atom 3 '(2 2 3 (4 2 4 (3) 3)4))
3
|
Probleme
Problema 1. Operaţii cu mulţimi.
Problema 2. Expresii logice cu NAND
Problema 3. Count-atom
|