PDF de programación - LISP I

Imágen de pdf LISP I

LISP Igráfica de visualizaciones

Actualizado el 18 de Mayo del 2020 (Publicado el 20 de Diciembre del 2017)
322 visualizaciones desde el 20 de Diciembre del 2017
116,4 KB
7 paginas
Creado hace 14a (29/09/2005)
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
  • Links de descarga
http://lwp-l.com/pdf7970

Comentarios de: LISP I (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad