LISP I

1

Programación recursiva frente a iterativa z

Características de la programación recursiva: » Implementación intuitiva y elegante. La traducción de la solución recursiva de un problema (caso base y caso recursivo) a código Lisp es prácticamente inmediata. » Útil para optimizar cálculos. Las estructuras de datos en Lisp hacen un uso implíctito de los punteros, como en las listas: – NIL ó – Un cons cuyo cdr es, a su vez, una lista

» Útil cuando hay varios niveles de anidamiento. La solución para un nivel es válida para el resto. z

Formas de hacer versión iterativa: » Con mapcar » Con bucles (dolist, dotimes, etc. Desaconsejado).

2

1

Ejemplos de recursividad, (1) z

Ejemplo del cálculo de la potencia de un número optimizada

> (defun potencia (x n) ;; “Optimizacion calculo potencia" (cond ((= n 0) 1) ((evenp n) (expt (potencia x (/ n 2)) 2) ) (t (* x (potencia x (- n 1)))))) > (potencia 2 3) 8

z

La interpretación y comprensión del código es compleja. Por ello es importante llegar a un compromiso entre la claridad de la programación y la eficiencia en la misma. 3

Ejemplos de recursividad, (2) z

Contar los átomos de cualquier expresión LISP:

> (cuenta-atomos '(a (b c) ((d e) f))) 6 > (defun cuenta-atomos (expr) (cond ((null expr) 0) ((atom expr) 1) (t (+ (cuenta-atomos (first expr)) (cuenta-atomos (rest expr))))))

4

2

Ejemplos de recursividad, (3) z

Aplanar una lista: » (aplana ‘(a (b c) ((d e) f))) >>> (A B C D E F) > (defun aplana (lista) (cond ((null lista) NIL) ((atom (first lista)) (cons (first lista) (aplana (rest lista)))) (t (append (aplana (first lista)) (aplana (rest lista))))))

5

Ejemplos de recursividad, (4) z

Número de sublistas de una lista (número de veces que se abre paréntesis, menos 1): » (sublistas ‘(a (b c) ((d e) f))) >>> 3 > (defun sublistas (expresion) (cond ((or (null expresion) (atom expresion)) 0) (t (+ (if (atom (first expresion)) 0 1) (sublistas (first expresion)) (sublistas (rest expresion))))))

6

3

Ejemplos de recursividad, (5) z

Producto escalar: » (producto '(2 3) '(4 5)) >>> 23 » 2 x 4 + 3 x 5 = 23

z

Versiones válidas: » Versión recursiva: > (defun producto (vector1 vector2) (if (or (null vector1) (null vector2)) 0 (+ (* (first vector1) (first vector2)) (producto (rest vector1) (rest vector2)))))

» Versión con mapcar >(defun producto (vector1 vector2) (apply #'+ (mapcar #'* vector1 vector2)))

7

Ejemplos de recursividad, (6) z

Versión no válida del producto escalar: » Versión iterativa (no recomendable): > (defun producto (vector1 vector2) (let ((suma 0)) (dotimes (i (length vector1)) (setf suma (+ suma (* (nth i vector1) (nth i vector2))))) suma))

8

4

Ejemplos de recursividad, (7) > (defun profundidad-maxima (expresion) (cond ((null expresion) 0) ((atom expresion) 1) (t (+ 1 (apply #'max (mapcar #'profundidad-maxima expresion)))))) >>> PROFUNDIDAD-MAXIMA > (profundidad-maxima '(1)) >>>> 2 > (profundidad-maxima '((1 (2 (3))) 4)) >>>> 5

9

Repaso de operadores, (1) z

Recordemos los siguientes operadores: » COUNT-IF, FIND-IF, REMOVE-IF, REMOVE-IF-NOT, DELETE-IF, DELETE-IF-NOT » COUNT / COUNT-IF – Contar apariciones: z (count

[:test ]) » (count 2 ‘(1 2 3 4 2 4 5 2)) 3 – Contar los elementos que cumplen /no cumplen una condición de una lista z (count-if[-not]

» (count-if ‘oddp ‘(1 2 3 4 5 6)) 3 10

5

Repaso de operadores, (2) » FIND / FIND-IF – Devuelve la primera aparición: z (find

[:test ]) » (find 2 ‘(1 2 3 4 2 4 5 2)) 2 – Devuelve el primer elemento que cumple/o no cumple el predicado z (find-if[-not]

» (find-if ‘oddp '(1 2 3 4 2 4 5 2)) 1 » REMOVE / REMOVE-IF – Borrar las apariciones de un elemento indicado z (remove

[:test ]) » (remove 2 ‘(1 2 3 4 2 4 5 2)) (1 3 4 4 5) – Elimina los que cumple/o no cumple el predicado z (remove-if[-not]

» (remove-if ‘oddp '(1 2 3 4 2 4 5 2)) (2 4 2 4 2)

11

Ejemplos de recursividad, (8) z

Objetivo: sin utilizar remove-if, conseguir la misma funcionalidad del operador: » (quitar-si ‘evenp '(1 2 3 4)) (1 3)

z

Versiones válidas: » Versión recursiva: (defun quitar-si (predicado lista) (cond ((null lista) nil) ((funcall predicado (car lista)) (quitar-si predicado (cdr lista))) (t (cons (car lista) (quitar-si predicado (cdr lista))))))

» Versión con mapcar (defun quitar-si (predicado lista) (delete NIL (mapcar #'(lambda (elemento) (when (not (funcall predicado elemento)) elemento)) lista)))

12

6

Ejemplos de recursividad, (9) z

Recorriendo la lista con dolist:

(defun QUITAR-SI (predicado lista) (let (listaaux) (dolist (i lista listaaux) (if (not (eval (list predicado i))) (setf listaaux (append listaaux (list i))) ) ) ) )

13

Ejemplos de recursividad, (10) z

Versión errónea: » Mal uso de mapcar. El hecho de que hagamos uso de mapcar no garantiza la corrección del código programado.

(defun QUITAR-SI2 (predicado lista) (mapcar #’(lambda (elemento) (if (apply predicado (list elemento)) (remove elemento lista)) ) lista)) > (QUITAR-SI2 'evenp '(1 2 3 4)) (NIL (1 3 4) NIL (1 2 3))

14

7