Subiecte
Probleme
1. Implementaţi următoarele operaţii cu mulţimi: uniune, intersecţie, diferenţă, test de egalitate.
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.
Primitivele MAPCAR şi APPLY
Un mod cāteodetă 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 procedura la fiecare element al unei liste. MAPCAR va returna lista rezultatelor.
Sintaxa:
(mapcar <nume procedura>
<lista de argumente>)
Exemplu:
Evaluānd expresia:
(mapcar 'oddp'(1 2 3))
obţinem
(t nil t)
Aici mapcar produce execuţia iterativa a predicatului oddp pe fiecare element al listei. Rezultatele sunt colectate īntr-o listă.
APPLY aplică o procedură unei liste de argumente (nu fiecăruia īn parte cum face MAPCAR).
Sintaxa:
(apply <nume procedura>
<lista argumente>)
Exemplu:
Dacă avem o listă de numere
(setq l '(4 7 2))
şi dorim să adunăm numerele din listă, ar fi greşit sa 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)
va returna 13.
Folosind MAPCAR şi APPLY īmpreună putem rezolva mult mai elegant probleme complex recursive.
Exemplu:
O implementare mai eficientă a procedurii COUNT-ATOMS (numără 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ăt'ime a arborelui generalizat.
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))))))
Primitiva MAPCAN se comportă ca şi MAPCAR combinat cu APPEND.
(MAPCAN <nume procedura> <lista argumente>)) ==
== (APPLY 'APPEND (MAPCAR <nume procedura> <lista argumente>))
Iteraţii folosind DO
DO are 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.
Exemplu:
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