PDF de programación - LISP I

LISP I

1

Programación recursiva frente

a iterativa

(cid:122) 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.

(cid:122) Formas de hacer versión iterativa:

» Con mapcar
» Con bucles (dolist, dotimes, etc.

Desaconsejado).

2

1

Ejemplos de recursividad, (1)

(cid:122) 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

(cid:122) 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)

(cid:122) 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)

(cid:122) 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)

(cid:122) 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)

(cid:122) Producto escalar:

» (producto '(2 3) '(4 5)) >>> 23
» 2 x 4 + 3 x 5 = 23
(cid:122) 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)

(cid:122) 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)

(cid:122) Recordemos los siguientes operadores:

» COUNT-IF, FIND-IF, REMOVE-IF,
REMOVE-IF-NOT, DELETE-IF,
DELETE-IF-NOT

» COUNT / COUNT-IF
– Contar apariciones:

(cid:122) (count <elemento> <lista>
[:test <fun-igualdad>])
» (count 2 ‘(1 2 3 4 2 4 5 2))

3

– Contar los elementos que cumplen /no cumplen

una condición de una lista

(cid:122) (count-if[-not] <predicado><lista>

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

3

10

5

Repaso de operadores, (2)

» FIND / FIND-IF

– Devuelve la primera aparición:
(cid:122) (find <elemento> <lista>

[:test <fun-igualdad>])
» (find 2 ‘(1 2 3 4 2 4 5 2))

– Devuelve el primer elemento que cumple/o no cumple

el predicado

(cid:122) (find-if[-not] <predicado><lista>

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

2

1

» REMOVE / REMOVE-IF

– Borrar las apariciones de un elemento indicado

(cid:122) (remove <elemento> <lista>

[:test <fun-igualdad>])
» (remove 2 ‘(1 2 3 4 2 4 5 2))

(1 3 4 4 5)

– Elimina los que cumple/o no cumple el predicado

(cid:122) (remove-if[-not] <predicado><lista>

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

(2 4 2 4 2)

11

Ejemplos de recursividad, (8)

(cid:122) Objetivo: sin utilizar remove-if, conseguir la

misma funcionalidad del operador:
» (quitar-si ‘evenp '(1 2 3 4))

(1 3)

(cid:122) 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)

(cid:122) 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)
(cid:122) 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