Programas de "Implementación de algoritmos y cálculo simbólico" (Curso 1991-92)

José A. Alonso Jiménez (jalonso@us.es)
Dpto. de Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla


Indice de programas:
		cuadrado ...............  2
		abs ....................  2
		m_o_m ..................  3
		raiz ...................  4
		fact ...................  5
		fib ....................  6
		ack .................... 11
		potencia ............... 14
		monedas ................ 16
		mcd .................... 17
		primos ................. 18
		sigma .................. 19
		producto ............... 20
		acumular ............... 22
		ej_let ................. 23
		raices ................. 24
		p_fijo ................. 25
		a_ratio ................ 25
		listas ................. 28
		map .................... 38
		cuenta_atomos .......... 40
		linealiza .............. 40
		reverse_total .......... 41
		subst .................. 42

;;;;; CUADRADO.LL
;;;;; Funciones elementales con cuadrados
;;;;; Basado en Abelson [90] p. 12-13

;;;; Ejercicio 1:
;;; Definir el procedimiento
;;;     (cuadrado x)
;;; que devuelva el cuadrado del número x.  Por ejemplo,
;;;     (cuadrado 3)  =>  9

(defun cuadrado (x)
       (* x x))

;;;; Ejercicio 2:
;;; Definir el procedimiento
;;;     (suma-de-cuadrados x y)
;;; que devuelva la suma de los cuadrados de x e y.  Por ejemplo,
;;;     (suma-de-cuadrados 3 4)  =>  25

(defun suma-de-cuadrados (x y)
       (+ (cuadrado x) (cuadrado y)))

;;;; Ejercicio 3:
;;; Definir el procedimiento
;;;     (f x)
;;; que devuelva el valor de
;;;     (x+1)^2 + (x+2)^2.
;;; Por ejemplo,
;;;     (f 2 2)  =>  25

(defun f (x)
       (suma-de-cuadrados (+ x 1) (+ x 2)))

========================================================================

;;;;; ABS.LL
;;;;; Valor absoluto
;;;;; Basado en Abelson [90] p. 17

;;;; Ejercicio :
;;; Definir el procedimiento
;;;     (abs x)
;;; que devuelva el valor absoluto de x.  Por ejemplo,
;;;     (abs -3)  =>  3
;;;
;;; Nota: el procedimiento abs está predefinido.

(defun abs (x)
       ;; Versión 1
       (cond ((> x 0) x)
             ((= x 0) x)
             ((< x 0) (- x))))

(defun abs (x)
       ;; Versión 2
       (cond ((< x 0) (- x))
             (t x)))

(defun abs (x)
       ;; Versión 3
       (if (< x 0)
           (- x)
           x))

========================================================================

;;;;; M_O_M.LL
;;;;; Comparación de números
;;;;; Basado en Abelson [90] p. 18

;;;; Ejercicio 1:
;;; Definir el procedimiento
;;;     (menor-o-igualp x y)
;;; que devuelva t si x es menor o igual que y y (), en caso contrario.
;;; Por ejemplo,
;;;     (menor-o-igualp 2 3)  =>  t
;;;     (menor-o-igualp 4 3)  =>  ()

(defun menor-o-igualp (x y)
       ;; Versión 1
       (or (< x y) (= x y)))

(defun menor-o-igualp (x y)
       ;; Versión 2
       (not (> x y)))

========================================================================

;;;;; RAIZ.LL
;;;;; Cálculo de la raíz cuadrada por el método de Newton
;;;;; Basado en Abelson [90] p. 20-22

;;;; Ejercicio :
;;; Definir el procedimiento
;;;     (raiz-cuadrada x)
;;; que devuelva una aproximación de la raiz cuadrada de x obtenida por
;;; el método de Newton.

(defun raiz-cuadrada (x)
       (raiz-cuadrada-aux 1 x))

(defun raiz-cuadrada-aux (aproximacion x)
       (if (buena-aproximacionp aproximacion x)
           aproximacion
           (raiz-cuadrada-aux (mejora aproximacion x)
                 x)))

(defun mejora (aproximacion x)
       (media aproximacion (/ x aproximacion)))

(defun media (x y)
       (/ (+ x y) 2))

(defun buena-aproximacionp (aproximacion x)
       (< (abs (- (cuadrado aproximacion) x)) 0.001))

(defun abs (x)
       (if (< x 0)
           (- x)
           x))

(defun cuadrado (x)
       (* x x))

========================================================================

;;;;; FACT.LL
;;;;; La función factorial.
;;;;; Basado en Abelson [90] p. 30-33


;;;; Ejercicio 1:
;;; Definir el procedimiento
;;;     (factorial n)
;;; que devuelva el factorial del número n. Por ejemplo,
;;;     (factorial 3) => 6

(defun factorial (n)
       (if (= n 1)
           1
           (* n (factorial (- n 1)))))

;;;; Ejercicio 2:
;;; Escribir el proceso de evaluación de la expresión (factorial 4) con
;;; la definición anterior.

;;;; Solución:
;;; (factorial 4) =
;;; = (* 4 (factorial 3)) =
;;; = (* 4 (* 3 (factorial 2))) =
;;; = (* 4 (* 3 (* 2 (factorial 1)))) =
;;; = (* 4 (* 3 (* 2 (* 1 1)))) =
;;; = (* 4 (* 3 (* 2 1))) =
;;; = (* 4 (* 3 2)) =
;;; = (* 4 6) =
;;; = 24

;;;; Ejercicio 3:
;;; Determinar el número de veces que se llama a la función factorial
;;; durante el proceso de evaluación de (factorial n).

;;;; Solución:
;;; El número de llamadas a la función factorial en el proceso de
;;; cálculo de (factorial n) es n.

;;;; Ejercicio 4:
;;; Determinar el máximo número de átomos de las listas generadas en
;;; el proceso de evaluación de (factorial n).

;;;; Solución:
;;; La lista con el mayor número de átomos generada en el proceso de
;;; cálculo de (factorial n) es
;;;     (* n ( ...  (* 2 (factorial 1))))
;;; que tiene 2n átomos.

;;;; Ejercicio 5:
;;; El cálculo del factorial puede realizarse según el siguiente
;;; esquema:
;;;             Contador Resultado Número
;;;                1        1        4
;;;                2        1        4
;;;                3        2        4
;;;                4        6        4
;;;                5       24        4
;;; en el que se inicializan el contador y el reultado a 1 (línea 1) y
;;; en cada línea se aumenta el contador en uno y se hace el resultado
;;; igual al producto del contador y el resultado de la línea anterior.
;;; El proceso se hasta que el contador supera al número dado, en cuyo
;;; caso el valor del resultado es el factorial del número dado. Definir
;;; el procedimiento
;;;     (factorial-iter n)
;;; que devuelva el factorial n de forma que su proceso de evaluación se
;;; ajuste al esquema iterativo anterior.

(defun factorial-iter (n)
        (factorial-aux 1 1 n))

(defun factorial-aux (contador resultado numero)
       (if (> contador numero)
           resultado
           (factorial-aux (+ contador 1)
                          (* contador resultado)
                          numero)))

;;;; Ejercicio 6:
;;; Escribir el proceso de evaluación de la expresión
;;;     (factorial-iter 4)

;;;; Solución:
;;; (factorial-iter 4) =
;;; = (factorial-aux 1 1 4) =
;;; = (factorial-aux (+ 1 1) (* 1 1) 4) =
;;; = (factorial-aux 2 1 4) =
;;; = (factorial-aux (+ 2 1) (* 2 1) 4) =
;;; = (factorial-aux 3 2 4) =
;;; = (factorial-aux (+ 3 1) (* 3 2) 4) =
;;; = (factorial-aux 4 6 4) =
;;; = (factorial-aux (+ 4 1) (* 4 6) 4) =
;;; = (factorial-aux 5 24 4) =
;;; = 24

;;;; Ejercicio 7:
;;; Determinar el número de veces que se llama a la función
;;; factorial-aux durante el proceso de evaluación de
;;; (factorial-iter n).

;;;; Solución:
;;; El número de llamadas a la función factorial-aux en el proceso de
;;; cálculo de (factorial-iter n) es n+1.

;;;; Ejercicio 8:
;;; Determinar el máximo número de átomos de las listas generadas en
;;; el proceso de evaluación de (factorial-iter n), con n > 1.

;;;; Solución:
;;; La lista con el mayor número de átomos generada en el proceso de
;;; cálculo de (factorial-iter n) es de la forma
;;;     (factorial-aux (+ contador 1) (* contador resultado) n)
;;; que tiene 8 átomos.

========================================================================

;;;;; FIB.LL
;;;;; La función de Fibonacci.
;;;;; Basado en Abelson [90] p. 34-37

;;;; Ejercicio 1:
;;; La sucesión de Fibonacci
;;;     0, 1, 1, 2, 3, 5, 8, 13, 21, ...
;;; se obtiene partiendo de 0 y 1 y cada término es la suma de los dos
;;; anteriores. Definir el procedimiento
;;;     (fib n)
;;; que devuelva el valor del término n-ésimo de la sucesión. Por
;;; ejemplo,
;;;     (fib 0) => 0
;;;     (fib 6) => 8

(defun fib (n)
       (cond ((= n 0) 0)
             ((= n 1) 1)
             (t (+ (fib (- n 1))
                   (fib (- n 2))))))

;;;; Ejercicio 2:
;;; Escribir el proceso de evaluación de la expresión
;;;     (fib 4)

;;;; Solución:
;;; (fib 4) =
;;; = (+ (fib 3) (fib 2)) =
;;; = (+ (+ (fib 2) (fib 1)) (+ (fib 1) (fib 0))) =
;;; = (+ (+ (+ (fib 1) (fib 0)) 1) (+ 1 0)) =
;;; = (+ (+ (+ 1 0) 1) 1)
;;; = 3

;;;; Ejercicio 3:
;;; Representar el proceso anterior mediante el árbol de evaluación

;;;; Solución:
;;; Ver Abelson [90] p.36.

;;;; Ejercicio 4:
;;; Definir el procedimiento
;;;     (complejidad-de-fib n)
;;; que devuelva el número de veces que con la anterior definición se
;;; calcula (fib 0) o (fib 1) para calcular (fib n). Por ejemplo,
;;;     (complejidad-de-fib 4) => 5.

(defun complejidad-de-fib (n)
       (cond ((= n 0) 1)
             ((= n 1) 1)
             (t (+ (complejidad-de-fib (- n 1))
                   (complejidad-de-fib (- n 2))))))

;;;; Ejercicio 5:
;;; Calcular el valor de las siguientes expresiones:
;;; (1) (complejidad-de-fib 0)
;;; (2) (complejidad-de-fib 1)
;;; (3) (complejidad-de-fib 2)
;;; (4) (complejidad-de-fib 3)
;;; (5) (complejidad-de-fib 4)
;;; (6) (complejidad-de-fib 5)

;;;; Solución:
;;; (complejidad-de-fib 0) = 1
;;; (complejidad-de-fib 1) = 1
;;; (complejidad-de-fib 2) = 2
;;; (complejidad-de-fib 3) = 3
;;; (complejidad-de-fib 4) = 5
;;; (complejidad-de-fib 5) = 8

;;;; Ejercicio 6:
;;; Dar explícitamente el valor de (complejidad-de-fib n).

;;;; Solución:
;;; (complejidad-de-fib n) = fib(n+1).

;;;; Ejercicio 7:
;;; Sabiendo que fib(n) es el entero más próximo a c^n/2, donde
;;; c = (1 + sqrt(5))/2 es el número áureo. Definir
;;;     (fib-fla n)
;;; que devuelva el valor de fib(n) usando dicha fórmula.
;;; [Nota: usar las funciones primitivas:
;;;     (power x y)
;;; que devuelve el valor de x^y. Por ejemplo,
;;;     (power 2 3) => 8
;;; y
;;;     (truncate x)
;;; que devuelve el valor de x sin los decimales. Por ejemplo,
;;;     (truncate 2.6) => 2].

(defun fib-fla (n)
       (aproxima (/ (power (/ (+ 1 (sqrt 5)) 2)
                           n)
                     2)))

(defun aproxima (x)
       (if (<= (- x (truncate x)) 0.5)
           (truncate x)
           (+ (truncate x) 1)))

;;;; Ejercicio 8:
;;; ¿Cómo crece el tiempo al calcular (fib n)?.

;;;; Solución:
;;; O(fib(n)) = O(c^n), crecimiento exponencial.

;;;; Ejercicio 9:
;;; Definir el procedimiento
;;;     (tiempo-fib n)
;;; que devuelva los segundos necesarios para calcular (fib n).
;;; [Nota: usar los procedimientos predefinidos
;;;     (gc)
;;; que libera la memoria y
;;;     (runtime)
;;; que devuelve el tiempo (en segundos) de CPU utilizado desde el
;;; comienzo de la sesión].

(defun tiempo-fib (n)
       (gc)
       (setf tiempo-inicial (runtime))
       (fib n)
       (- (runtime) tiempo-inicial))

;;;; Ejercicio 10:
;;; Calcular el valor de las siguientes expresiones:
;;; (1) (tiempo-fib 14)
;;; (2) (tiempo-fib 15)
;;; (3) (tiempo-fib 16)
;;; (4) (tiempo-fib 17)
;;; (5) (tiempo-fib 18)
;;; (6) (tiempo-fib 19)
;;; (7) (tiempo-fib 20)

;;;; Solución:
;;; (tiempo-fib 14) => 0.11
;;; (tiempo-fib 15) => 0.16
;;; (tiempo-fib 16) => 0.27
;;; (tiempo-fib 17) => 0.44
;;; (tiempo-fib 18) => 0.76
;;; (tiempo-fib 19) => 1.26
;;; (tiempo-fib 20) => 2.08

;;;; Ejercicio 11:
;;; Comprobar la relación entre el crecimiento de (tiempo-fib n) y la
;;; sucesión de Fibonacci.

;;;; Solución:
;;; (- (tiempo-fib 15) (tiempo-fib 14)) =>  5
;;; (- (tiempo-fib 16) (tiempo-fib 15)) => 11
;;; (- (tiempo-fib 17) (tiempo-fib 16)) => 17
;;; (- (tiempo-fib 18) (tiempo-fib 17)) => 32
;;; (- (tiempo-fib 19) (tiempo-fib 18)) => 50
;;; (- (tiempo-fib 20) (tiempo-fib 19)) => 82

;;;; Ejercicio 12:
;;; El valor de fib(n) puede calcularse mediante el siguiente proceso
;;; iterativo:
;;;     contador a  b número
;;;        0     1  0   6
;;;        1     1  1   6
;;;        2     2  1   6
;;;        3     3  2   6
;;;        4     5  3   6
;;;        5     8  5   6
;;;        6    13  8   6
;;; en el que se inicializa el contador a 0, a a 1 y b a 0.  En cada
;;; paso, el contador se incrementa en 1, el valor de a es la suma de
;;; los anteriores valores de a y b, y el valor de b es el anterior
;;; valor de a.  Siguiendo el proceso, si el valor del contador es n,
;;; entonces el valor de a es fib(n+1) y el valor de b es fib(n).
;;; Definir el procedimiento
;;;     (fib-iter n)
;;; que devuelva el valor de fib(n) calculado imitando el anterior
;;; proceso iterativo.

(defun fib-iter (n)
       (fib-iter-aux 0 1 0 n))

(defun fib-iter-aux (contador a b numero)
       (if (= contador numero)
           b
           (fib-iter-aux (+ contador 1) (+ a b) a numero)))

;;;; Ejercicio 13:
;;; Escribir el proceso de evaluación de la expresión
;;;     (fib-iter 4)

;;;; Solución:
;;; (fib-iter 4) =
;;; = (fib-iter-aux 0 1 0 4) =
;;; = (fib-iter-aux 1 1 1 4) =
;;; = (fib-iter-aux 2 2 1 4) =
;;; = (fib-iter-aux 3 3 2 4) =
;;; = (fib-iter-aux 4 5 3 4) =
;;; = 3

;;;; Ejercicio 14:
;;; Definir el procedimiento
;;;     (tiempo-fib-iter n)
;;; que devuelva los segundos necesarios para calcular (fib-iter n).

(defun tiempo-fib-iter (n)
       (setf tiempo-inicial (runtime))
       (fib-iter n)
       (- (runtime) tiempo-inicial))

;;;; Ejercicio 15:
;;; Calcular el valor de las siguientes expresiones:
;;; (1) (tiempo-fib-iter 14)
;;; (2) (tiempo-fib-iter 15)
;;; (3) (tiempo-fib-iter 16)
;;; (4) (tiempo-fib-iter 17)
;;; (5) (tiempo-fib-iter 18)
;;; (6) (tiempo-fib-iter 19)
;;; (7) (tiempo-fib-iter 20)

;;;; Solución:
;;; (tiempo-fib-iter 14) => 0.
;;; (tiempo-fib-iter 15) => 0.
;;; (tiempo-fib-iter 16) => 0.
;;; (tiempo-fib-iter 17) => 0.
;;; (tiempo-fib-iter 18) => 0.
;;; (tiempo-fib-iter 19) => 0.
;;; (tiempo-fib-iter 20) => 0.

;;;; Ejercicio 16:
;;; Definir el procedimiento
;;;     (tabla-fib)
;;; que devuelva una sucesión de valores de la forma
;;;     fib(0) = 0
;;;     fib(1) = 1
;;;     fib(2) = 1
;;;     fib(3) = 2
;;;     ...
;;; [Nota; usar la función predefinida
;;;     (print <expresion 1> ... <expresion n>)
;;; que escribe los valores de la expresiones <expresion 1>, ...,
;;; <expresion n>. Por ejemplo,
;;;     (print "fib(" (+ 1 3) ") = " 3)
;;; escribe
;;;     fib(4) = 3].

(defun tabla-fib ()
       (tabla-fib-aux 0))

(defun tabla-fib-aux (n)
       (print "fib(" n ") = " (fib n))
       (tabla-fib-aux (+ n 1)))

;;;; Ejercicio 17:
;;; Definir análogamente el procedimiento
;;;     (tabla-fib-iter).

(defun tabla-fib-iter ()
       (tabla-fib-iter-aux 0))

(defun tabla-fib-iter-aux (n)
       (print "fib-iter(" n ") = " (fib-iter n))
       (tabla-fib-iter-aux (+ n 1)))

;;;; Ejercicio 18:
;;; Comparar le eficiencia de los procedimientos fib y fib-iter
;;; evaluando con el ordenador las expresiones (tabla-fib) y
;;; (tabla-fib-iter).
;;; [Nota: Antes de cargar el fichero fib.ll, cargar la librería
;;; ratio.ll].

;;;; Solución:
;;; El procedimiento fib calcula, lentamente, hasta (fib 30). El
;;; procedimineto fib-iter calcula, rápidamente, hasta (fib-iter 1000).

========================================================================

;;;;; ACK.LL
;;;;; La función de Ackermann.
;;;;; Basado en Abelson [90] p. 34

;;;; Ejercicio 1:
;;; La función de Ackermann está definida por:
;;;     A(0,y) = y+1;
;;;     A(x,0) = A(x-1,1), si x>0;
;;;     A(x,Y) = A(x-1,A(x,y-1)), si x>0 e y>0.
;;; Definir el procedimiento
;;;     (a x y)
;;; que devuelva el valor de A(x,y).

(defun a (x y)
       (cond ((= x 0) (+ y 1))
             ((= y 0) (a (- x 1) 1))
             (t (a (- x 1)
                   (a x (- y 1))))))

;;;; Ejercicio 2:
;;; Evaluar las siguientes expresiones:
;;; (1) (a 1 0)
;;; (2) (a 1 1)
;;; (3) (a 1 2)

;;;; Solución:
;;; (a 1 0) =
;;; = (a 0 1) =
;;; = 2
;;;
;;; (a 1 1) =
;;; = (a 0 (a 1 0)) =
;;; = (a 0 2) =
;;; = 3
;;;
;;; (a 1 2) =
;;; = (a 0 (a 1 1)) =
;;; = (a 0 3) =
;;; = 4

;;;; Ejercicio 3:
;;; Sea f(n) = A(1,n). Definir f(n) explícitamente.

;;;; Solución:
;;; Probaremos por inducción que
;;;     f(n) = n+2.
;;;
;;; Base: n=0:
;;;     f(0) = A(1,0) =
;;;          = A(0,1) =
;;;          = 2.
;;;
;;; Paso: n |--> n+1:
;;;     f(n+1) = A(1, n+1) =
;;;            = A(0, A(1, n)) =
;;;            = A(0, n+2)
;;;            = n+3 =
;;;            = (n+1)+2.

;;;; Ejercicio 4:
;;; Definir el procedimiento
;;;     (f n)
;;; que devuelva el valor de A(1,n) de forma que su proceso de cálculo
;;; no sea recursivo.

(defun f (n)
       (+ n 2))

;;;; Ejercicio 5:
;;; Evaluar las siguientes expresiones:
;;; (1) (a 2 1)
;;; (2) (a 2 2)
;;; (3) (a 2 3)

;;; Solución:
;;; (a 2 1) =
;;; = (a 1 (a 2 0)) =
;;; = (a 1 3) =
;;; = 5
;;;
;;; (a 2 2) =
;;; = (a 1 (a 2 1)) =
;;; = (a 1 5) =
;;; = 7
;;;
;;; (a 2 3) =
;;; = (a 1 (a 2 2))
;;; = (a 1 7) =
;;; = 9

;;;; Ejercicio 6:
;;; Sea g(n) = A(2,n). Definir g(n) explícitamente.

;;;; Solución:
;;; Vamos a demostrar por inducción que
;;;     g(n) = 2n+3.
;;;
;;; Base n = 0:
;;;     g(n) = A(2,0) =
;;;          = A(1,1) =
;;;          = A(0,A(1,0)) =
;;;          = A(0,A(0,1)) =
;;;          = A(0,2) =
;;;          = 3.
;;;
;;; Paso n |--> n+1:
;;;     g(n+1) = A(2,n+1) =
;;;            = A(1,A(2,n)) =
;;;            = A(1,2n+3) =
;;;            = A(0,A(1,2n+2)) =
;;;            = A(0,f(2n+2)) =
;;;            = A(0,2n+4) =
;;;            = 2n+5 =
;;;            = 2(n+1)+3.

;;;; Ejercicio 7:
;;; Evaluar las siguientes expresiones:
;;; (1) (a 3 0)
;;; (2) (a 3 1)
;;; (3) (a 3 2)
;;; (4) (a 3 3)

;;;; Solución:
;;; (a 3 0) =
;;; = (a 2 1) =
;;; = 5
;;;
;;; (a 3 1) =
;;; = (a 2 (a 3 0)) =
;;; = (a 2 5) =
;;; = 13
;;;
;;; (a 3 2) =
;;; = (a 2 (a 3 1) =
;;; = (a 2 13) =
;;; = 29

========================================================================

;;;;; POTENCIA.LL
;;;;; Cálculo de potencia de exponente entero positivo.
;;;;; Basado en Abelson [90] p. 41-42.

;;;; Ejercicio 1:
;;; Definir el procedimiento
;;;     (potencia a n)
;;; que devuelva el valor de a elevado a n (donde n es un número entero
;;; positivo). Por ejemplo,
;;;     (potencia 2 3)  =>  8.
;;; [Nota: En LeLisp, la función predefinida equivalente es
;;; (power x y)].

(defun potencia (a n)
       (if (= n 0)
           1
           (* a (potencia a (- n 1)))))

;;;; Ejercicio 2:
;;; Determinar la complejidad en tiempo y espacio del procedimiento
;;; potencia

;;;; Solución:
;;; La complejidad en tiempo y espacio de potencia es O(n).

;;;; Ejercicio
;;; El valor de 2^3 puede calculare mediante el siguiente proceso
;;; iterativo
;;;             base contador resultado
;;;              2      3        1
;;;              2      2        2
;;;              2      1        4
;;;              2      0        8
;;; en el que se inicializa el contador al valor del exponente y el
;;; resultado a 1. En cada paso, el contador se disminuye en 1 y el
;;; resultado se sustituye por el producto de la base y el resultado
;;; anterior. El proceso continúa hasta que el contador vale 0, en cuyo
;;; caso el valor de resultado es la potencia buscada. Definir el
;;; procedimiento,
;;;     (potencia-iter a n)
;;; que devuelva el valor de a^n calculado imitando el anterior proceso
;;; iterativo.
;;; [Nota: Observar la invarianza de la relación
;;;     base^contador*resultado = a^n].

(defun potencia-iter (a n)
       (potencia-iter-aux a n 1))

(defun potencia-iter-aux (base contador resultado)
       (if (= contador 0)
           resultado
           (potencia-iter-aux base
                              (- contador 1)
                              (* base resultado))))

;;;; Ejercicio 3:
;;; Determinar la complejidad en tiempo y espacio del procedimiento
;;; potencia-iter.

;;;; Solución:
;;; La complejidad en tiempo de potencia-iter es O(n).
;;; La complejidad en espacio de potencia-iter es O(1).

;;;; Ejercicio 4:
;;; Definir el procedimiento
;;;     (potencia-rapida a n)
;;; que devuelva el valor de a^n utilizando las siguientes relaciones:
;;;     a^n = (a^(n/2))^2, si n es par
;;;     a^n = a*a^(n-1),   si n es impar
;;; [Nota: usar el predicado predefinido
;;;     (evenp x)
;;; que devuelve x, si x es un número par y (), en caso contrario].

(defun potencia-rapida (a n)
       (cond ((= n 0) 1)
             ((evenp n) (cuadrado (potencia-rapida a (/ n 2))))
             (t (* a (potencia-rapida a (- n 1))))))

(defun cuadrado (x)
       (* x x))

;;;; Ejercicio 5:
;;; Escribir el proceso de cálculo de
;;;     (potencia-rapida 2 8)

;;;; Solución:
;;; (potencia-rapida 2 8) =
;;; = (cuadrado (potencia-rapida 2 4)) =
;;; = (cuadrado (cuadrado (potencia-rapida 2 2))) =
;;; = (cuadrado (cuadrado (cuadrado (potencia-rapida 2 1)))) =
;;; = (cuadrado (cuadrado (cuadrado (* 2 (potencia-rapida 2 0))))) =
;;; = (cuadrado (cuadrado (cuadrado (* 2 1)))) =
;;; = (cuadrado (cuadrado (cuadrado 2))) =
;;; = (cuadrado (cuadrado 4)) =
;;; = (cuadrado 16) =
;;; = 256

;;;; Ejercicio 6:
;;; Determinar la complejidad en tiempo y espacio del procedimiento
;;; potencia-rapida.

;;;; Solución:
;;; La complejidad en tiempo y espacio de potencia es O(log n).

;;;; Ejercicio 7:
;;; Completar la siguiente tabla con los tiempos empleados en el
;;; cálculo, utilizando la librería ratio:
;;;                   | 2^100 | 2^200 | 2^300 | 2^400 | 2^500
;;;    ---------------|-------|-------|-------|-------|------
;;;    potencia       |       |       |       |       |
;;;    ---------------|-------|-------|-------|-------|------
;;;    potencia-iter  |       |       |       |       |
;;;    ---------------|-------|-------|-------|-------|------
;;;    potencia-rapida|       |       |       |       |

========================================================================

;;;;; MONEDAS.LL
;;;;; Problema de cambios de monedas.
;;;;; Basado en Abelson [90] p. 37-39.

;;;; Ejercicio:
;;; Definir el procedimiento
;;;     (numero-de-cambios n)
;;; que devuelva el número de formas de cambiar n pesetas usando monedas
;;; de 1, 5, 10, 25 y 50 pesetas. Por ejemplo,
;;;     (numero-de-cambios 10) => 4
;;; ya que 10 = 1(10) = 2(5) = 1(5)+5(1) = 10(1).

(defun numero-de-cambios (n)
       (ndc n 5))

(defun ndc (n tipos-de-monedas)
       (cond ((or (= n 0) (= tipos-de-monedas 1)) 1)
             ((< n 0) 0)
             (t (+ (ndc (- n
                          (primera-clase tipos-de-monedas))
                        tipos-de-monedas)
                   (ndc n
                        (- tipos-de-monedas 1))))))

(defun primera-clase (tipos-de-monedas)
       (cond ((= tipos-de-monedas 1) 1)
             ((= tipos-de-monedas 2) 5)
             ((= tipos-de-monedas 3) 10)
             ((= tipos-de-monedas 4) 25)
             ((= tipos-de-monedas 5) 50)))

;;;; Ejercicio 2:
;;; Calcular el valor de
;;;     (numero-de-cambios 10)
;;; utilizando la definición anterior.

;;;; Solución:
;;; (numero-de-cambios 10) =
;;; = (ndc 10 5) =
;;; = (+ (ndc -40 5) (ndc 10 4)) =
;;; = (+ 0 (+ (ndc -15 4) (ndc 10 3))) =
;;; = (+ 0 (+ 0 (+ (ndc 0 3) (ndc 10 2)))) =
;;; = (+ 0 (+ 0 (+ 1 (+ (ndc 5 2) (ndc 10 1))))) =
;;; = (+ 0 (+ 0 (+ 1 (+ (+ (ndc 0 2) (ndc 5 1)) 1)))) =
;;; = (+ 0 (+ 0 (+ 1 (+ (+ 1 1) 1)))) =
;;; = 4

;;;; Ejercicio 3:
;;; Representar el cálculo anterior mediante el árbol de evaluación.

;;;; Ejercicio 4:
;;; Definir el procedimiento
;;;     (tabla-de-numero-de-cambios x y z)
;;; que devuelva los números de cambios para los valores comprendidos
;;; x e y, con paso z. Por ejemplo,
;;;     ? (tabla-de-numero-de-cambios 10 50 5)
;;;     numero-de-cambios(10) = 4
;;;     numero-de-cambios(15) = 6
;;;     numero-de-cambios(20) = 9
;;;     numero-de-cambios(25) = 13
;;;     numero-de-cambios(30) = 18
;;;     numero-de-cambios(35) = 24
;;;     numero-de-cambios(40) = 31
;;;     numero-de-cambios(45) = 39
;;;     numero-de-cambios(50) = 50
;;;     = fin

(defun tabla-de-numero-de-cambios (x y z)
       (cond ((<= x y)
              (print "numero-de-cambios("
                     x
                     ") = "
                     (numero-de-cambios x))
              (tabla-de-numero-de-cambios (+ x z) y z))
             (t 'fin)))

========================================================================

;;;;; MCD.LL
;;;;; Máximo común divisor.
;;;;; Basado en Abelson [90] p. 44

;;;; Ejercicio 1:
;;; Definir el procedimiento
;;;     (mcd x y)
;;; que devuelva el máximo común divisor de x e y. Por ejemplo,
;;;     (mcd 6 10)  =>  2

(defun mcd (x y)
       (if (= y 0)
           x
           (mcd y (modulo x y))))

;;;; Ejercicio 2:
;;; Determinar la complejidad en espacio y tiempo del procedimiento mcd.

;;;; Solución:
;;; La complejidad en espacio de mcd es O(1).
;;; La complejidad en tiempo de mcd es O(log n).

========================================================================

;;;;; PRIMOS.LL
;;;;; Cálculo de números primos.
;;;;; Basado en Abelson [90] p. 45-49.

;;;; Ejercicio 1:
;;; Definir el procedimiento
;;;     (menor-divisor n)
;;; que devuelva el menor entero (mayor que 1) que divida a n. Por
;;; ejemplo,
;;;     (menor-divisor 35)  =>  5

(defun menor-divisor (n)
       (menor-divisor-aux n 2))

(defun menor-divisor-aux (n x)
       (cond ((> (cuadrado x) n) n)
             ((dividep x n) x)
             (t (menor-divisor-aux n (+ x 1)))))

(defun cuadrado (x)
       (* x x))

(defun dividep (x y)
       ;; x es un divisor de y
       (= (modulo y x) 0))

;;;; Ejercicio 2:
;;; Usar el procedimiento menor-divisor para calcular los menores
;;; divisores de los siguientes números: 199, 1999, 19999.

;;;; Solución:
;;; (menor-divisor 199)   => 199
;;; (menor-divisor 1999)  => 1999
;;; (menor-divisor 19999) => 7

;;;; Ejercicio 3:
;;; Definir el procedimiento
;;;     (primop n)
;;; que devuelva t si n es primo y (), en caso contrario.

(defun primop (n)
       (if (= n (menor-divisor n))
           t
           ()))

;;;; Ejercicio 4:
;;; Dos números a y b son congruentes módulo n si dan el mismo resto al
;;; dividirlos por n. El teorema de Fermat afirma:
;;;
;;; Si n es un número primo, entonces para todo a menor que n, a^n  es
;;; congruente con a módulo n.
;;;
;;; Por ejemplo, para n = 5,
;;;     1^5 =    1 = 1 (mod 5)
;;;     2^5 =   32 = 2 (mod 5)
;;;     3^5 =  243 = 3 (mod 5)
;;;     4^5 = 1024 = 4 (mod 5)
;;;
;;; Definir los siguientes procedimientos:
;;;     (potencia-mod a n m)
;;; que devuelva el valor de a^n módulo m;
;;;     (test-de-fermat n)
;;; que eliga un número aleatorio a en el intervalo [2, n[ y devuelva t
;;  si a^n es congruente con a módulo n y (), en caso contrario;
;;;     (primop-rapido n m)
;;; que devuelva t, si n verifica m tests de Fermat y (), en caso
;;; contrario.
;;; [Nota: usar el procedimiento predefinido
;;;     (random x y)
;;; que devuelve un número aleatorio en el intervalo [x,y[].

(defun potencia-mod (a n m)
       (cond ((= n 0) 1)
             ((evenp n)
              (modulo (cuadrado (potencia-mod a (/ n 2) m))
                      m))
             (t (modulo (* a (potencia-mod a (- n 1) m))
                        m))))

(defun test-de-fermat (n)
       (setf a (random 2 (- n 2)))
       (= (potencia-mod a n n) a))

(defun primop-rapido (n m)
       (cond ((= m 0) t)
             ((test-de-fermat n)
              (primop-rapido n (- m 1)))
             (t ())))

========================================================================

;;;;; SIGMA.LL
;;;;; Suma de series.
;;;;; Basado en Abelson [90] p. 52

;;;; Ejercicio 1:
;;; Definir el procedimiento
;;;     (suma-enteros a b)
;;; que devuelva el valor de la suma de los enteros comprendidos entre
;;; a y b.  Por ejemplo,
;;;     (suma-enteros 2 5)  =>  14

(defun suma-enteros (a b)
       (if (> a b)
           0
           (+ a (suma-enteros (+ a 1) b))))

;;;; Ejercicio 2:
;;; Definir el procedimiento
;;;     (suma-cubos a b)
;;; que devuelva el valor de la suma de los cubos de los enteros
;;; comprendidos entre a y b. Por ejemplo,
;;;     (suma-cubos 2 5)  => 224

(defun suma-cubos (a b)
       (if (> a b)
           0
           (+ (cubo a) (suma-cubos (+ a 1) b))))

(defun cubo (n)
       (* n n n))


;;;; Ejercicio 3:
;;; El número pi puede calcularse mediante la siguiente fórmula:
;;;     pi = 8 * (1/(1*3) + 1/(5*7) + 1/(9*11) + ...)
;;; Definir el procedimiento
;;;     (suma-pi a b)
;;; que devuelva el valor de ls suma
;;;     1/(a*(a+2)) + 1/((a+4)*(a+6)) +...+ 1/((a+n)*(a+n+2))
;;; hasta que a+n+4 > b. Por ejemplo,
;;;     (* 8 (suma-pi 1 1000))  =>  3.13593

(defun suma-pi (a b)
       (if (> a b)
           0
           (+ (/ 1 (* a(+ a 2))) (suma-pi (+ a 4) b))))

;;;; Ejercicio 4:
;;; Definir el procedimiento
;;;     (suma a b s f)
;;; que devuelva el valor de
;;;     f(a) + f(s(a)) + f(s(s(a)) + ... + f(s(...(s(a))...))
;;; hasta que s(s(...(s(a))...)) > b. Por ejemplo,
;;;     (suma 2 5 '1+ 'cubo)  =>  224
;;; [Nota 1: El valor de
;;;     '<símbolo>
;;; es el propio <símbolo>. Por ejemplo,
;;;     'a  =>  a].
;;; [Nota 2: Utilizar el procedimiento
;;;     (funcall f e)
;;; que devuelve el valor de aplicar la función f a la expresión e. Por
;;; ejemplo,
;;;     (funcall '1+ 3)  => 4 ].

(defun suma (a b s f)
       (if (> a b)
           0
           (+ (funcall f a)
              (suma (funcall s a) b s f))))

;;;; Ejercicio 6:
;;; Describir el proceso de cálculo de
;;;     (suma 2 4 '1+ 'cuadrado)
;;; donde cuadrado es el procedimiento definido por
;;;     (defun cubo (x) (* x x x))

;;;; Solución:
;;; (suma 2 4 '1+ 'cubo) =
;;; = (+ (funcall 'cubo 2) (suma (funcall '1+ 2) 4 '1+ 'cubo)) =
;;; = (+ 8 (suma 3 4 '1+ 'cubo)) =
;;; = (+ 8 (+ (funcall 'cubo 3) (suma (funcall '1+ 3) 4 '1+ 'cubo))) =
;;; = (+ 8 (+ 27 (suma 4 4 '1+ 'cubo))) =
;;; = (+ 8 (+ 27 (+ (funcall 'cubo 4)
;;;                 (suma (funcall '1+ 4) 4 '1+ 'cubo)))) =
;;; = (+ 8 (+ 27 (+ 64 (suma 5 4 '1+ 'cubo)))) =
;;; = (+ 8 (+ 27 (+ 64 0))) =
;;; = (+ 8 (+ 27 64)) =
;;; = (+ 8 91) =
;;; = 99

;;;; Ejercicio 6:
;;; Utilizando el procedimiento suma, redefinir los procedimientos
;;; anteriores. Es decir,
;;;     (suma-enteros-2 a b)
;;;     (suma-cubos-2 a b)
;;;     (suma-pi-2 a b)

(defun suma-enteros-2 (a b)
       (suma a b '1+ '1+))

(defun suma-cubos-2 (a b)
       (suma a b '1+ 'cubo))

(defun suma-pi-2 (a b)
       (suma a b '4+ 'f-pi))

(defun 4+ (x)
       (+ x 4))

(defun f-pi (x)
       (/ 1 (* x (+ x 2))))

;;;; Ejercicio 7:
;;; Definir el procedimiento
;;;     (suma-iter a b s f)
;;; que devuelva el mismo valor que (suma a b s f) pero empleando un
;;; proceso de cálculo iterativo

(defun suma-iter (a b s f)
       (suma-iter-aux a b s f 0))

(defun suma-iter-aux (a b s f r)
       (if (> a b)
           r
           (suma-iter-aux (funcall s a) b s f (+ (funcall f a) r))))

;;;; Ejercicio 8:
;;; Definir el procedimiento
;;;     (suma-pi-3 a b)
;;; que devuelva el mismo valor que (suma-pi a b) pero usando el
;;; procedimiento suma-iter y funciones anónimas.

(defun suma-pi-3 (a b)
       (suma-iter a
                  b
                  '(lambda (x) (+ x 4))
                  '(lambda (x) (/ 1 (* x (+ x 2))))))

;;;; Ejercicio 9:
;;; La integral definida de una función f entre los límites a y b puede
;;; aproximarse numéricamente usando la fórmula
;;;     (f(a+h/2) + f(a+h+h/2) + f(a+2h+h/2) + ... )h
;;; para valores pequeños de h. Definir el procedimiento
;;;     (integral a b f h)
;;; que devuelva el valor de dicha expresión. Por ejemplo,
;;;     (integral 0 1 'cubo 0.01)   =>  0.2399875
;;;     (integral 0 1 'cubo 0.001)  =>  0.2499999

(defun integral (a b f h)
       (* (suma-iter (+ a (/ h 2))
                     b
                     '(lambda (x) (+ x h))
                     f)
          h))

;;;; Ejercicio 10:
;;; Utilizar el procedimiento integral para calcular el valor de la
;;; integral entre 0 y 1 de las siguientes funciones:
;;; (1) f(x) = x^4
;;; (2) g(x) = 3x^2 + 4x^3

;;;; Solución:
;;; (integral 0 1 '(lambda (x) (* x x x x)) 0.01)
;;;         =>  0.1999833
;;; (integral 0 1 '(lambda (x) (+ (* 3 x x)( * 4 x x x))) 0.01)
;;;         => 1.999925

;;;; Ejercicio 11:
;;; La integral definida de una función f entre los límites a y b puede
;;; aproximarse numéricamente usando la siguiente fórmula (conocida como
;;; fórmula de los trapecios (Demidovich p.409)):
;;;     ((f(a) + f(b))/2 + f(a+h) + f(a+2h) + ... + f(a+(n-1)h))h
;;; donde h = (b-a)/n. (Aumentando n, se mejora la aproximación).
;;; Definir el procedimiento
;;;     (integral-trapecios a b f n)
;;; que devuelva el valor de dicha expresión. Por ejemplo,
;;;     (integral-trapecios 0 1 'cubo 100)   =>  0.240322
;;;     (integral-trapecios 0 1 'cubo 1000)  =>  0.2490032

(defun integral-trapecios (a b f n)
       (setf h (/ (- b a) n))
       (* (+ (/ (+ (funcall f a) (funcall f b)) 2)
             (suma-iter (+ a h)
                        (+ a (* (- n 1) h))
                        '(lambda (x) (+ x h))
                        f))
          h))

;;;; Ejercicio 12:
;;; Aplicar el procedimiento anterior par resolver los ejercicios
;;; 3163-3172 de Demidovich "Problemas y ejercicios de análisis
;;; matemático".

========================================================================

;;;;; PRODUCTO.LL
;;;;; Producto de términos
;;;;; Basado en Abelson [90] p. 56

;;;; Ejercicio 1:
;;; Definir el procedimiento
;;;     (producto a b s f)
;;; que devuelva el valor de
;;;     f(a) * f(s(a)) * f(s(s(a)) * ... * f(s(...(s(a))...))
;;; hasta que s(s(...(s(a))...)) > b. Por ejemplo,
;;;     (producto 2 5 '1+ '(lambda (x) x))  =>  120

(defun producto (a b s f)
       (if (> a b)
           1
           (* (funcall f a)
              (producto (funcall s a) b s f))))

;;;; Ejercicio 2:
;;; Definir el procedimiento
;;;     (producto-iter a b s f)
;;; que devuelva el mismo valor que (suma a b s f) pero empleando un
;;; proceso de cálculo iterativo

(defun producto-iter (a b s f)
       (producto-iter-aux a b s f 1))

(defun producto-iter-aux (a b s f r)
       (if (> a b)
           r
           (producto-iter-aux (funcall s a)
                              b
                              s
                              f
                              (* (funcall f a) r))))

;;;; Ejercicio 3:
;;; Definir, usando el procedimiento producto-iter, el procedimiento
;;;     (factorial n)
;;; que devuelva el factorial de n.
;;; [Nota: usar el procedimiento
;;;     (identity x)
;;; que devuelve el valor de x. Por ejemplo,
;;;     (identity 3)  =>  3].

(defun factorial (n)
       (producto-iter 1 n '1+ 'identity))

;;;; Ejercicio 4:
;;; Definir el procedimiento
;;;     (producto-pi a b)
;;; que devuelva el valor del producto
;;;       a(a+2)     (a+2)(a+4)          (a+n)(a+n+2)
;;;     ---------- * ---------- * ... * --------------
;;;     (a+1)(a+1)   (a+3)(a+3)         (a+n+1)(a+n+1)
;;; hasta que a+n+2 > b. Utilizar el procedimiento para obtener
;;; aproximaciones de pi utilando la fórmula de Wallis
;;;    pi    2.4   4.6   6.8
;;;    -- =  --- * --- * --- * ....
;;;    4     3.3   5.5   7.7

(defun producto-pi (a b)
       (producto-iter a
                      b
                      '(lambda (x) (+ x 2))
                       '(lambda (x) (/ (* x (+ x 2))
                                       (* (+ x 1) (+ x 1))))))

;;;; Solución:
;;; (* 4 (producto-pi 2 10))   =>  3.275101
;;; (* 4 (producto-pi 2 100))  =>  3.15703
;;; (* 4 (producto-pi 2 1000)) =>  3.143161

========================================================================

;;;;; ACUMULAR.LL
;;;;; Abstracción de sumatorio y productorio.
;;;;; Basado en Abelson [90] p. 56

;;;; Ejercicio:
;;; La suma (SIGMA.LL) y producto (PROD.LL) son casos especiales de un
;;; procedimiento más general
;;;     (acumular a b s f combinar valor-nulo)
;;; de forma que
;;;     (suma     a b s f) = (acumular a b s f '+ 0)
;;;     (producto a b s f) = (acumular a b s f '* 1)
;;; Definir el procedimiento acumular (en forma recursiva e iterativa) y
;;; utilizarlo para redefinir los procedimientos suma y producto.
;;; Comprobar que
;;;     (suma          2 5 '1+ 'identity)  =>  14
;;;     (producto      2 5 '1+ 'identity)  =>  120
;;;     (suma-iter     2 5 '1+ 'identity)  =>  14
;;;     (producto-iter 2 5 '1+ 'identity)  =>  120

(defun acumular (a b s f combinar valor-nulo)
       (if (> a b)
           valor-nulo
           (funcall combinar
                    (funcall f a)
                    (acumular (funcall s a)
                              b
                              s
                              f
                              combinar valor-nulo))))

(defun suma (a b s f)
       (acumular a b s f '+ 0))

(defun producto (a b s f)
       (acumular a b s f '* 1))

(defun acumular-iter (a b s f combinar valor-nulo)
       (acumular-iter-aux a b s f combinar valor-nulo valor-nulo))

(defun acumular-iter-aux (a b s f combinar valor-nulo r)
       (if (> a b)
           r
           (acumular-iter-aux (funcall s a)
                              b
                              s
                              f
                              combinar
                              valor-nulo
                              (funcall combinar r (funcall f a)))))

(defun suma-iter (a b s f)
       (acumular-iter a b s f '+ 0))

(defun producto-iter (a b s f)
       (acumular-iter a b s f '* 1))

========================================================================

;;;;; EJ_LET.LL
;;;;; Ejemplo de utilización del procedimiento let.
;;;;; Basado en Abelson [90] p. 58.

;;;; Ejercicio 1:
;;; Definir el procedimiento
;;;     (f x y)
;;; que devuelva el valor de
;;;     x(1+xy)^2+y(1-y)+(1+xy)(1-y)
;;; Por ejemplo,
;;;     (f 2 1) => 18

(defun f (x y)
       (let ((a (+ 1 (* x y)))
             (b (- 1 y)))
            (+ (* x (* a a))
               (* y b)
               (* a b))))

========================================================================

;;;;; RAICES.LL
;;;;; Cálculo de raíces de ecuaciones mediante el método de bipartición.
;;;;; Basado en Abelson [90] p. 62-63.

;;;; Ejercicio 1:
;;; El método de bipartición para encontrar las raíces de una ecuación
;;; f(x) = 0, donde f es una función continua se basa en la siguiente
;;; idea:
;;;
;;; Si a y b dos puntos tales que f(a) < 0 < f(b), entonces f tiene un
;;; cero entre a y b. Para buscarlo, sea c = (a+b)/2. Si f(c) = 0,
;;; entonces f tiene un cero en c; si f(c) > 0, entonces f tiene un cero
;;; entre a y c; si f(c) < 0, entonces f tiene un cero entre c y b.
;;; Continuando este proceso se puede buscar la raíz de f(x) = 0, con la
;;; precisión deseada (i.e. hasta que |a-b| sea menor que un número
;;; dado).
;;;
;;; Definir el procedimiento
;;;     (buscar f a b)
;;; de forma que si f es una función continua, a es un punto tal que
;;; f(a) < 0 y b es un punto tal que f(b) > 0, devuelva una raíz de la
;;; ecuación f(x) = 0 con un error de 0.001. Por ejemplo,
;;;     (buscar '(lambda (x) (- (* x x) 4)) 0 4)  =>  1.999878

(defun buscar (f a b)
       (let ((c (/ (+ a b) 2)))
            (if (bastante-cercap a b)
                c
                (let ((fc (funcall f c)))
                     (cond ((> fc 0) (buscar f a c))
                           ((< fc 0) (buscar f c b))
                           (t c))))))

(defun bastante-cercap (a b)
       (< (abs (- a b)) 0.001))

;;;; Ejercicio 2:
;;; Definir el procedimiento
;;;     (metodo-biparticion f a b)
;;; de forma que si f es una función continua y a y b son dos puntos,
;;; devuelva una raíz de la ecuación f(x) = 0 con un error de 0.001, si
;;; los valores de f en a y b tienen signos distintos y el mensaje "Los
;;; valores tienen el mismo signo", en caso contrario. Por ejemplo,
;;;     (metodo-biparticion 'sin 2 4)  =>  3.14111328

========================================================================

;;;;; P_FIJO.LL
;;;;; Cálculo de puntos fijos.
;;;;; Basado en Abelson [90] p. 67

;;;; Ejercicio:
;;; Un número x se llama punto fijo de una función f si se verifica la
;;; ecuación f(x) = x. Para algunas funciones (como por ejemplo el
;;; coseno) puede localizarse un punto fijo comenzando por un valor a y
;;; aplicando f repetidamente,
;;;     f(a), f(f(a)), f(f(f(a))), ...
;;; hasta que |f(a) - a| es suficientemente pequeño. Usando esta idea,
;;; definir el procedimiento
;;;     (punto-fijo f a)
;;; que devuelva una aproximación a un punto fijo de la función f.
;;; Comprobar el procedimiento verificando que
;;;     (punto-fijo 'cos 1)
;;; da una aproximación de un punto fijo de la función coseno.

(defun punto-fijo (f a)
       (if (buena-aproximacionp f a)
           a
           (punto-fijo f (funcall f a))))

(defun buena-aproximacionp (f a)
       (< (abs (- (funcall f a) a)) 0.001))

;;;; Comprobación:
;;; (punto-fijo 'cos 1)  =>  0.7395672
;;; (cos 0.7395672)      =>  0.7387603

========================================================================

;;;;; A_RATIO.LL
;;;;; Aritmética racional
;;;;; Basado en Abelson [90] p.75

;;;; Ejercicio 1: (Representación I)
;;; Vamos a representar los números racionales por pares de números
;;; enteros. Por ejemplo, el número 2/5 lo representaremos por el par
;;; (2 . 5).
;;;
;;; Definir los procedimientos:
;;;     (crea-rat n d)
;;; que devuelva el número racional cuyo numerador es el número entero
;;; n y cuyo denominador es el número entero d,
;;;     (numerador x)
;;; que devuelva el denominador del número racional x, y
;;;     (denominador x)
;;; que devuelva el denominador del número racional x. Por ejemplo,
;;;     (setf x (crea-rat 2 5))  =>  (2 . 5)
;;;     x                        =>  (2 . 5)
;;;     (numerador x)            =>  2
;;;     (denominador x)          =>  5
;;;
;;; Nota: Usar los procedimientos predefinidos
;;;     (cons n m)
;;; que devuelve el par formado por el valor de x y el valor de y,
;;;     (car x)
;;; que devuelve el primer elemento del par x, y
;;;     (cdr x)
;;; que devuelve el segundo elemento del par x. Por ejemplo,
;;;     (setf x (cons 2 5))  =>  (2 . 5)
;;;     (car x)              =>  2
;;;     (cdr x)              =>  5

(defun crea-rat (n d) (cons n d))

(defun numerador (x) (car x))

(defun denominador (x) (cdr x))

;;;; Ejercicio 2: (Operaciones aritméticas)
;;; Definir los procedimientos
;;;     (+rat x y)
;;; que devuelva la suma de los números racionales x e y,
;;;     (-rat x y)
;;; que devuelva la diferencia de los números racionales x e y,
;;;     (*rat x y)
;;; que devuelva el producto de los números racionales x e y,
;;;     (/rat x y)
;;; que devuelva el cociente de los números racionales x e y,
;;;     (=rat x y)
;;; que devuelva t si los números racionales x e y son iguales y (), en
;;; caso contrario. Por ejemplo,
;;;     (setf un-medio  (crea-rat 1 2))  =>  (1 . 2)
;;;     (setf un-tercio (crea-rat 1 3))  =>  (1 . 3)
;;;     (+rat un-medio un-tercio)        =>  (5 . 6)
;;;     (*rat un-medio un-tercio)        =>  (1 . 6)
;;;     (+rat un-tercio un-tercio)       =>  (6 . 9)

(defun +rat (x y)
       (crea-rat (+ (* (numerador x) (denominador y))
                    (* (numerador y) (denominador x)))
                 (* (denominador x) (denominador y))))

(defun -rat (x y)
       (crea-rat (- (* (numerador x) (denominador y))
                    (* (numerador y) (denominador x)))
                 (* (denominador x) (denominador y))))

(defun *rat (x y)
       (crea-rat (* (numerador x) (numerador y))
                 (* (denominador x) (denominador y))))

(defun /rat (x y)
       (crea-rat (* (numerador x) (denominador y))
                 (* (denominador x) (numerador y))))

(defun =rat (x y)
       (if (= (* (numerador x) (denominador y))
              (* (denominador x) (numerador y)))
           t
           ()))

;;;; Ejercicio 3: (Representación II)
;;; Definir el procedimiento
;;;     (escribe-rat x)
;;; que escriba el número racional x con el formato
;;; numerador/denominador. Por ejemplo,
;;;     (setf un-medio  (crea-rat 1 2))        =>  (1 . 2)
;;;     (escribe-rat un-medio)                 =>  1/2
;;;     (setf un-tercio (crea-rat 1 3))        =>  (1 . 3)
;;;     (escribe-rat un-tercio)                  =>  1/3
;;;     (escribe-rat (+rat un-medio un-tercio))  =>  5/6
;;;     (escribe-rat (*rat un-medio un-tercio))  =>  1/6
;;;     (escribe-rat (+rat un-tercio un-tercio)) =>  6/9
;;;
;;; Nota: usar el procedimiento predefinido
;;;     (concat <cadena 1> ... <cadena n>)
;;; que devuelve el símbolo creado uniendo las cadenas <cadena 1>, ...,
;;; < cadena n>. Por ejemplo,
;;;     (concat (+ 1 4) "/" 6)  =>  5/6

(defun escribe-rat (x)
       (concat (numerador x) "/" (denominador x)))

;;;; Ejercicio 4: (Representación III)
;;; Modificar la definición del procedimiento
;;;     (crea-rat n d)
;;; para que simplifique el numerador y el denominador. Por ejemplo,
;;;     (crea-rat 6 9)                           =>  (2 . 3)
;;;     (escribe-rat (+rat un-tercio un-tercio)) =>  2/3

(defun crea-rat (n d)
       (let ((m (mcd n d)))
            (cons (/ n m) (/ d m))))

(defun mcd (x y)
       (if (= y 0)
           x
           (mcd y (modulo x y))))

;;;; Ejercicio 5:
;;; La anterior definición de crea-rat necesita que sus argumentos sean
;;; números enteros positivos. Redefinir
;;;     (crea-rat n d)
;;; para que admita argumentos negativos. Por ejemplo,
;;;     (crea-rat 6 -9)                =>  (-1 . 2)
;;;     (escribe-rat (crea-rat 6 -9))  =>  -2/3

(defun crea-rat (n d)
       (let ((m (mcd (abs n) (abs d))))
            (if (> (* n d) 0)
                (cons (/ (abs n) m) (/ (abs d) m))
                (cons (- (/ (abs n) m)) (/ (abs d) m)))))

(defun mcd (x y)
       (if (= y 0)
           x
           (mcd y (modulo x y))))

========================================================================

;;;;; LISTAS.LL
;;;;; Operaciones con listas.
;;;;; Basado en Abelson [90] p. 90-95

;;;; Ejercicio 1:
;;; Determinar el valor de las siguientes expresiones:
;;; (1) (cons 1 2)
;;; (2) (cons 1 nil)
;;; (3) (cons 2 (cons 1 nil))
;;; (4) (cons 3 (cons 2 (cons 1 nil)))
;;; (5) (list 3 2 1)

;;;; Solución:
;;; (1) (cons 1 2)                       =>  (1 . 2)
;;; (2) (cons 1 nil)                     =>  (1)
;;; (3) (cons 2 (cons 1 nil))            =>  (2 1)
;;; (4) (cons 3 (cons 2 (cons 1 nil)))   =>  (3 2 1)
;;; (5) (list 3 2 1)                     =>  (3 2 1)

;;;; Ejercicio 2:
;;; Determinar el valor de las siguientes expresiones:
;;; (1) a
;;; (2) (setf a 1)
;;; (3) b
;;; (4) (setf b 2)
;;; (5) (list a b)
;;; (6) (a b)
;;; (7) (list 'a 'b)
;;; (8) 'a
;;; (9) '(a b)

;;;; Solución:
;;; (1) a               => Error: variable indefinida: a
;;; (2) (setf a 1)      => 1
;;; (3) a               => 1
;;; (4) (setf b 2)      => 2
;;; (5) (list a b)      => (1 2)
;;; (6) (a b)           => Error: función indefinida: a
;;; (7) (list 'a 'b)    => (a b)
;;; (8) 'a              => a
;;; (9) '(a b)          => (a b)

;;;; Ejercicio 3:
;;; Determinar el valor de las siguientes expresiones:
;;; (1) (car '(a b c d))
;;; (2) (cdr '(a b c d))
;;; (3) (car (cdr '(a b c d)))
;;; (4) (cadr '(a b c d))
;;; (5) (cons e '(a b c d))

;;;; Solución:
;;; (1) (car '(a b c d))        =>  a
;;; (2) (cdr '(a b c d))        =>  (b c d)
;;; (3) (car (cdr '(a b c d)))  =>  b
;;; (4) (cadr '(a b c d))       =>  b
;;; (5) (cons 7 '(a b c d))     =>  (e a b c d)

;;;; Nota: Ilustrarlo con la notación de cajas-y-punteros.

;;;; Ejercicio 4:
;;; Definir el procedimiento
;;;     (segundo l)
;;; que devuelva el segundo elemento de la lista l. Por ejemplo,
;;;     (segundo '(a b c))  =>  b

(defun segundo (l)
       (car (cdr l)))

;;;; Ejercicio 5 (Abelson [90] p. 92):
;;; Definir el procedimiento
;;;     (nth n l)
;;; que devuelva el n-ésimo elemento de la lista l, numerando los
;;; elementos de la lista a partir de 0. Por ejemplo,
;;;     (nth 2 '(a b c d))  =>  c
;;;
;;; Nota: El procedimiento nth está predefinido.

(defun nth (n l)
       (if (= n 0)
           (car l)
           (nth (- n 1) (cdr l))))

;;;; Ejercicio 6:
;;; Describir el proceso de evaluación de
;;;     (nth 2 '(a b c d))  =>  c

;;;; Solución:
;;; (nth 2 '(a b c d)) =
;;; = (nth 1 '(b c d)) =
;;; = (nth 0 '(c d)) =
;;; = c

;;;; Ejercicio 7:
;;; Determinar la complejidad en espacio y tiempo del procedimiento
;;; nth.

;;;; Solución:
;;; La complejidad de (nth n l) es de O(1) en espacio y de O(n) en
;;; tiempo.

;;;; Ejercicio 8 (Chailloux [86] p. 3-48):
;;; Definir el procedimiento
;;;     (makelist n e)
;;; que cree una lista con n veces el elemento e. Por ejemplo,
;;;     (makelist 3 'a)  =>  (a a a)
;;;
;;; Nota: El procedimiento makelist está predefinido.

(defun makelist (n e)
       (if (= n 0)
           ()
           (cons e (makelist (- n 1) e))))

;;;; Ejercicio 9:
;;; Escribir el proceso de evaluación de
;;;     (makelist 3 'a)

;;;; Solución:
;;; (makelist 3 'a) =
;;; = (cons 'a (makelist 2 'a)) =
;;; = (cons 'a (cons 'a (makelist 1 'a))) =
;;; = (cons 'a (cons 'a (cons 'a (makelist 0 'a)))) =
;;; = (cons 'a (cons 'a (cons 'a ()))) =
;;; = (cons 'a (cons 'a '(a))) =
;;; = (cons 'a '(a a)) =
;;; = (a a a)

;;;; Ejercicio 10:
;;; Determinar la complejidad en espacio y tiempo del procedimiento
;;; makelist.

;;;; Solución:
;;; La complejidad de (makelist n l) es de O(n) en espacio y de O(n) en
;;; tiempo.

;;;; Ejercicio 11:
;;; Definir el procedimiento
;;;     (makelist-iter n e)
;;; que cree una lista con n veces el elemento e mediante un proceso
;;; iterativo. Por ejemplo,
;;;     (makelist-iter 3 'a)  =>  (a a a)

(defun makelist-iter (n e)
       (makelist-iter-aux n e ()))

(defun makelist-iter-aux (n e r)
       (if (= n 0)
           r
           (makelist-iter-aux (- n 1) e (cons e r))))

;;;; Ejercicio 12:
;;; Escribir el proceso de evaluación de
;;;     (makelist-iter 3 'a)

;;;; Solución:
;;; (makelist-iter 3 'a) =
;;; = (makelist-iter-aux 3 'a ()) =
;;; = (makelist-iter-aux 2 'a '(a)) =
;;; = (makelist-iter-aux 1 'a '(a a)) =
;;; = (makelist-iter-aux 0 'a '(a a a)) =
;;; = (a a a)

;;;; Ejercicio 13:
;;; Determinar la complejidad en espacio y tiempo del procedimiento
;;; makelist-iter.

;;;; Solución:
;;; La complejidad de (makelist n l) es de O(1) en espacio y de O(n) en
;;; tiempo.

;;;; Ejercicio 14 (Abelson [90] p. 92):
;;; Definir el procedimiento
;;;     (length l)
;;; que devuelva el número de elementos de la lista l. Por ejemplo,
;;;     (length '(a b c))       =>  3
;;;
;;; Nota 1: Utilizar el procedimiento predefinido
;;;     (null l)
;;; que devuelve t si l es la lista vacía y (), en caso contrario.
;;;
;;; Nota 2: El procedimiento length está predefinido.

(defun length (l)
       (if (null l)
           0
           (+ 1 (length (cdr l)))))

;;;; Ejercicio 15:
;;; Escribir el proceso de evaluación de la expresión
;;;     (length '(a b c))

;;;; Solución:
;;; (length '(a b c) =
;;; = (+ 1 (length '(b c)) =
;;; = (+ 1 (+ 1 (length '(c))) =
;;; = (+ 1 (+ 1 (+ 1 (length '()))) =
;;; = (+ 1 (+ 1 (+ 1 0))) =
;;; = 3

;;;; Ejercicio 16:
;;; Determinar la complejidad en espacio y tiempo del procedimiento
;;; length.

;;;; Solución:
;;; La complejidad de (length l) es de O(n) en espacio y de O(n) en
;;; tiempo.

;;;; Ejercicio 17 (Abelson [90] p. 93):
;;; Definir el procedimiento
;;;     (length-iter l)
;;; que devuelva el número de elementos de la lista l calculado mediante
;;; un proceso iterativo. Por ejemplo,
;;;     (length-iter '(a b c))       =>  3

(defun length-iter (l)
       (length-iter-aux l 0))

(defun longitud-iter-aux (l r)
       (if (null l)
           r
           (length-iter-aux (cdr l) (+ 1 r))))

;;;; Ejercicio 18:
;;; Escribir el proceso de evaluación de la expresión
;;;     (length-iter '(a b c))

;;;; Solución:
;;; (length-iter '(a b c)) =
;;; = (length-iter-aux '(a b c) 0) =
;;; = (length-iter-aux '(b c) 1) =
;;; = (length-iter-aux '(c) 2) =
;;; = (length-iter-aux '() 3) =
;;; = 3

;;;; Ejercicio 19:
;;; Determinar la complejidad en espacio y tiempo del procedimiento
;;; length-iter.

;;;; Solución:
;;; La complejidad de (length-iter l) es de O(1) en espacio y de O(n) en
;;; tiempo.

;;;; Ejercicio 20 (Abelson [90] p. 94 y Chailloux [86] p. 3-49):
;;; Definir el procedimiento
;;;     (reverse l)
;;; que devuelva la lista de los elementos de l en orden inverso. Por
;;; ejemplo,
;;;     (reverse '(a b c))       =>  (c b a)
;;;
;;; Nota: El procedimiento reverse está predefinido.

(defun reverse (l)
       (reverse-aux l ()))

(defun reverse-aux (l r)
       (if (null l)
           r
           (reverse-aux (cdr l) (cons (car l) r))))

;;;; Ejercicio 21:
;;; Escribir el proceso de evaluación de la expresión
;;;     (reverse '(a b c))

;;;; Solución:
;;; (reverse '(a b c)) =
;;; = (reverse-aux '(a b c) '()) =
;;; = (reverse-aux '(b c) '(a)) =
;;; = (reverse-aux '(c) '(b a)) =
;;; = (reverse-aux '() '(c b a)) =
;;; = '(c b a)

;;;; Ejercicio 22:
;;; Determinar la complejidad en espacio y tiempo del procedimiento
;;; reverse.

;;;; Solución:
;;; La complejidad de (reverse l) es de O(1) en espacio y de O(n)
;;; en tiempo.

;;;; Ejercicio 23:
;;; Definir el procedimiento
;;;     (ultimo l)
;;; que devuelva el último elemento de la lista l. Por ejemplo,
;;;     (ultimo '(a b c))  =>  c

(defun ultimo (l)
       (car (reverse l)))

;;;; Ejercicio 24 (Abelson [90] p. 93):
;;; Definir el procedimiento
;;;     (last l)
;;; que devuelva la lista formada con el último elemento de la lista l.
;;; Por ejemplo,
;;;     (last '(a b c))  =>  (c)
;;;
;;; Nota: El procedimiento last está predefinido.

(defun last (l)
       (list (ultimo l)))

;;;; Ejercicio 25:
;;; Definir el procedimiento
;;;     (penultimo l)
;;; que devuelva el último elemento de la lista l. Por ejemplo,
;;;     (penultimo '(a b c))  =>  b

(defun penultimo (l)
       (cadr (reverse l)))

;;;; Ejercicio 26 (Abelson [90] p. 93):
;;; Definir el procedimiento
;;;     (append l1 l2)
;;; que devuelva el resultado de concatenar la listas l1 y l2. Por
;;; ejemplo,
;;;     (append '(a b) '(c d e))  =>  (a b c d e)
;;;
;;; Nota: El procedimiento append está predefinido.

(defun append (l1 l2)
       (if (null l1)
           l2
           (cons (car l1) (append (cdr l1) l2))))

;;;; Ejercicio 27:
;;; Escribir el proceso de evaluación de la expresión
;;;     (append '(a b) '(c d e))

;;;; Solución:
;;; (append '(a b) '(c d e)) =
;;; = (cons 'a (append '(b) '(c d e))) =
;;; = (cons 'a (cons 'b (append '() '(c d e)))) =
;;; = (cons 'a (cons 'b '(c d e))) =
;;; = (cons 'a '(b c d e)) =
;;; = (a b c d e)

;;;; Ejercicio 28:
;;; Determinar la complejidad en espacio y tiempo del procedimiento
;;; append.

;;;; Solución:
;;; La complejidad de (append l1 l2) es de O(n) en espacio y de O(n) en
;;; tiempo, donde n es la longitud de l1.

;;;; Ejercicio 29:
;;; Definir el procedimiento
;;;     (append-iter l1 l2)
;;; que devuelva el resultado de concatenar la listas l1 y l2 calculado
;;; mediante un proceso iterativo. Por ejemplo,
;;;     (append-iter '(a b) '(c d e))  =>  (a b c d e)

(defun append-iter (l1 l2)
       (append-iter-aux (reverse l1) l2 l2))

(defun append-iter-aux (l1 l2 r)
       (if (null l1)
           r
           (append-iter-aux (cdr l1) l2 (cons (car l1) r))))

;;;; Ejercicio 30:
;;; Escribir el proceso de evaluación de la expresión
;;;     (append-iter '(a b) '(c d e))

;;;; Solución:
;;; (append-iter '(a b) '(c d e)) =
;;; = (append-iter-aux '(b a) '(c d e)) =
;;; = (append-iter-aux '(a) '(b c d e)) =
;;; = (append-iter-aux '() '(a b c d e)) =
;;; = (a b c d e)

;;;; Ejercicio 31:
;;; Determinar la complejidad en espacio y tiempo del procedimiento
;;; append-iter.

;;;; Solución:
;;; La complejidad de (append-iter l1 l2) es de O(1) en espacio y
;;; de O(n) en tiempo, donde n es la longitud de l1.

;;;; Ejercicio 32 (Abelson [90] p. 94):
;;; Definir el procedimiento
;;;     (reverse-rec l)
;;; que calcule la inversa de la lista l mediante un proceso recursivo.
;;; Por ejemplo,
;;;     (reverse-rec '(a b c))  =>  (c b a)

(defun reverse-rec (l)
       (if (null l)
           ()
           (append (reverse-rec (cdr l))
                   (list (car l)))))

;;;; Ejercicio 33:
;;; Escribir el proceso de evaluación de
;;;     (reverse-rec '(a b c))

;;;; Solución:
;;; (reverse-rec '(a b c)) =
;;; = (append (reverse-rec '(b c)) '(a)) =
;;; = (append (append (reverse-rec '(c)) '(b)) '(a)) =
;;; = (append (append (append (reverse-rec ()) '(c)) '(b)) '(a)) =
;;; = (append (append (append () '(c)) '(b)) '(a)) =
;;; = (append (append '(c) '(b)) '(a)) =
;;; = (append '(c b) '(a)) =
;;; = (c b a)

;;;; Ejercicio 34:
;;; Definir el procedimiento
;;;     (firstn n l)
;;; que devuelva una copia de los n primeros elementos de la lista l.
;;; Por ejemplo,
;;;     (firstn 2 '(a b c))  =>  (a b)
;;;
;;; Nota: El procedimiento firstn está predefinido.

(defun firstn (n l)
       (firstn-aux n l ()))

(defun firstn-aux (n l r)
       (if (= n 0)
           (reverse r)
           (firstn-aux (- n 1)
                       (cdr l)
                       (cons (car l) r))))

;;;; Ejercicio 35 (Chailloux [86] p. 3-50):
;;; Definir el procedimiento
;;;     (lastn n l)
;;; que devuelva una copia de los n últimos elementos de la lista l.
;;; Por ejemplo,
;;;     (lastn 2 '(a b c))  =>  (b c)
;;;
;;; Nota: El procedimiento lastn está predefinido.

(defun lastn (n l)
       (reverse (firstn n (reverse l))))

;;;; Ejercicio 36:
;;; Definir el procedimiento
;;;     (last l)
;;; que devuelva la lista formada por el último elemento de la lista l.
;;; Por ejemplo,
;;;     (last (list 1 2 3))  =>  (3)
;;;
;;; Nota: El procedimiento last está predefinido.

(defun last (l)
       (lastn 1 l))

;;;; Ejercicio 37 (Abelson [90] p. 103 y Wertz [86] p. 27-28):
;;; El procedimiento
;;;     (= n1 n2)
;;; compara los números n1 y n2; por ejemplo,
;;;     (= 2 (+ 1 1))  =>  2
;;;     (= 'a 'a)      =>  Error
;;;     (= '(1) '(1))  =>  Error
;;; El procedimiento
;;;     (eq s1 s2)
;;; compara átomos; por ejemplo,
;;;     (eq 'a 'a)      =>  t
;;;     (eq 1 1)        =>  t
;;;     (eq '(a) '(a))  =>  Error
;;;     (eq () ())      =>  t
;;;
;;; Definir el procedimiento
;;;     (equal e1 e2)
;;; que devuelva t si las expresiones e1 y e2 son iguales y (), en caso
;;; contrario. Por ejemplo,
;;;     (equal '(a) '(a))  =>  t
;;; Nota 1: Utilizar el predicado
;;;     (atom e)
;;; que devuelve t si e es un átomo y (), en caso contrario.
;;;
;;; Nota 2: El procedimiento equal está predefinido.

(defun equal (e1 e2)
       (if (atom e1)
           (eq e1 e2)
           (and (not (atom e2))
                (equal (car e1) (car e2))
                (equal (cdr e1) (cdr e2)))))

;;;; Ejercicio 38 (Abelson [90] p. 102 y Chailloux [86] p. 3-44):
;;; Definir el procedimiento
;;;     (memq a l)
;;; que devuelva la parte de la lista l que empieza por la primera
;;; ocurrencia del átomo a en l, si a es un elemento de l; y (), en
;;; caso contrario. Por ejemplo,
;;;     (memq 'b '(a b c b))    =>  (b c b)
;;;     (memq 'x '(a b c b))    =>  ()
;;;     (memq '(b) '(a (b) c))  =>  ()
;;;
;;; Nota: El procedimiento memq está predefinido.

(defun memq (a l)
       (cond ((null l) ())
             ((eq a (car l)) l)
             (t (memq a (cdr l)))))

;;;; Ejercicio 39:
;;; Definir el procedimiento
;;;     (member e l)
;;; que devuelva la parte de la lista l que empieza por la primera
;;; ocurrencia de la expresión e en l, si e es un elemento de l; y (),
;;; en caso contrario. Por ejemplo,
;;;     (member 'b '(a b c b))    =>  (b c b)
;;;     (member 'x '(a b c b))    =>  ()
;;;     (member '(b) '(a (b) c))  =>  ((b) c)
;;;
;;; Nota: El procedimiento member está predefinido.

(defun member (e l)
       (cond ((atom l) ())
             ((equal e (car l)) l)
             (t (member e (cdr l)))))

;;;; Ejercicio 40 (Chailloux [86] p. 3-52):
;;; Definir el procedimiento
;;;     (remove e l)
;;; que devuelva la lista obtenida a partir de la lista l borrando
;;; sus elementos iguales a la expresión e. Por ejemplo,
;;;     (remove 'b '(a b c b))    =>  (a c)
;;;     (remove 'x '(a b c b))    =>  (a b c b)
;;;     (remove 'b '(a (b) c b))  =>  (a (b) c)
;;;
;;; Nota: El procedimiento remove está predefinido.

(defun remove (e l)
       (cond ((atom l) l)
             ((equal e (car l)) (remove e (cdr l)))
             (t (cons (car l) (remove e (cdr l))))))

;;;; Ejercicio 41:
;;; Definir el procedimiento
;;;     (remove-iter e l)
;;; que devuelva el mismo resultado que (remove e l), pero calculado
;;; mediante un proceso iterativo.

(defun remove-iter (e l)
       (remove-iter-aux e (reverse l) ()))

(defun remove-iter-aux (e l r)
       (cond ((atom l) r)
             ((equal e (car l)) (remove-iter-aux e (cdr l) r))
             (t (remove-iter-aux e (cdr l) (cons (car l) r)))))

========================================================================

;;;;; MAP.LL
;;;;; Procedimientos aplicativos
;;;;; Basado en Abelson [90] p. 94-95

;;;; Ejercicio 1 (Abelson [90] p. 94):
;;; Definir el procedimiento
;;;     (lista-al-cuadrado l)
;;; de forma que, si l es una lista de números, devuelva la lista de los
;;; cuadrados de los elementos de l. Por ejemplo,
;;;     (lista-al-cuadrado '(1 2 3 4))  =>  (1 4 9 16)

(defun lista-al-cuadrado (l)
       (if (null l)
           ()
           (cons (cuadrado (car l))
                 (lista-al-cuadrado (cdr l)))))

(defun cuadrado (x)
       (* x x))

;;;; Ejercicio 2 (Abelson [90] p. 94):
;;; Definir el procedimiento
;;;     (lista-al-cuadrado-iter l)
;;; de forma que, si l es una lista de números, devuelva la lista de los
;;; cuadrados de los elementos de l; pero mediante un proceso iterativo.
;;; Por ejemplo,
;;;     (lista-al-cuadrado-iter '(1 2 3 4))  =>  (1 4 9 16)

(defun lista-al-cuadrado-iter (l)
       (lista-al-cuadrado-iter-aux l ()))

(defun lista-al-cuadrado-iter-aux (l r)
       (if (null l)
           (reverse r)
           (lista-al-cuadrado-iter-aux (cdr l)
                                       (cons (cuadrado (car l)) r))))

(defun cuadrado (x)
       (* x x))

;;;; Ejercicio 3 (Abelson [90] p. 95):
;;; Definir el procedimiento
;;;     (mapcar f l)
;;; de forma que, si f es una función y l es una lista, devuelve la
;;; lista obtenida aplicando f a todos los elementos de l. Por ejemplo,
;;;     (mapcar 'cuadrado '(1 2 3 4))  =>  (1 4 9 16)
;;;
;;; Nota: El procedimiento mapcar está predefinido.

(defun mapcar (f l)
       (if (null l)
           ()
           (cons (funcall f (car l))
                 (mapcar f (cdr l)))))

;;;; Ejercicio 4 (Abelson [90] p. 95):
;;; Definir el procedimiento
;;;     (mapcar-iter f l)
;;; de forma que, si f es una función y l es una lista, devuelve la
;;; lista obtenida aplicando f a todos los elementos de l. Por ejemplo,
;;;     (mapcar-iter 'cuadrado '(1 2 3 4))  =>  (1 4 9 16)

(defun mapcar-iter (f l)
       (mapcar-iter-aux f l ()))

(defun mapcar-iter-aux (f l r)
       (if (null l)
           (reverse r)
           (mapcar-iter-aux f
                            (cdr l)
                            (cons (funcall f (car l)) r))))

;;;; Ejercicio 5:
;;; Definir el procedimiento
;;;     (lista-al-cubo l)
;;; de forma que, si l es una lista de números, devuelva la lista de los
;;; cubos de los elementos de l. Por ejemplo,
;;;     (lista-al-cubo '(1 2 3 4))  =>  (1 8 27 64)

(defun lista-al-cubo (l)
       (mapcar '(lambda (x) (* x x x)) l))

========================================================================

;;;;; CUENT_AT.LL
;;;;; El procedimiento cuenta-atomos
;;;;; Basado en Abelson [90] p. 98

;;;; Ejercicio 1 (Abelson [90] p. 98):
;;; Definir el procedimiento
;;;     (cuenta-atomos e)
;;; que devuelva el número de átomos de la expresión e. Por ejemplo
;;;     (cuenta-atomos ())          =>  0
;;;     (cuenta-atomos 'a)          =>  1
;;;     (cuenta-atomos '((a b) a))  =>  3

(defun cuenta-atomos (e)
       (cond ((null e) 0)
             ((atom e) 1)
             (t (+ (cuenta-atomos (car e))
                   (cuenta-atomos (cdr e))))))

;;;; Ejercicio 2:
;;; Definir el procedimiento
;;;     (cuenta-atomos-map e)
;;; que devuelva el número de átomos de la expresión e, utilizando el
;;; procedimiento mapcar. Por ejemplo
;;;     (cuenta-atomos-map ())          =>  0
;;;     (cuenta-atomos-map 'a)          =>  1
;;;     (cuenta-atomos-map '((a b) a))  =>  3
;;;
;;; Nota: Utilizar el procedimiento
;;;     (apply f l)
;;; que devuelve el valor de aplicar la función f tomando los elementos
;;; de la lista l como argumentos. Por ejemplo,
;;;     (apply '+ '(2 3))  =>  5

(defun cuenta-atomos-map (e)
       (cond ((null e) 0)
             ((atom e) 1)
             (t (apply '+ (mapcar 'cuenta-atomos-map e)))))

========================================================================

;;;;; LINEALIZ.LL
;;;;; El procedimiento linealiza
;;;;; Basado en Abelson [90] p. 99

;;;; Ejercicio 1 (Abelson [90] p. 99):
;;; Definir el procedimiento
;;;     (linealiza e)
;;; que devuelva una lista cuyos elementos son los átomos de la
;;; expresión e. Por ejemplo,
;;;     (linealiza ())              =>  ()
;;;     (linealiza 'a)              =>  (a)
;;;     (linealiza '((a b) (c d)))  =>  (a b c d)

(defun linealiza (l)
       (cond ((null l) ())
             ((atom l) (list l))
             (t (append (linealiza (car l))
                        (linealiza (cdr l))))))

;;;; Ejercicio 2:
;;; Definir el procedimiento
;;;     (linealiza-map e)
;;; que devuelva una lista cuyos elementos son los átomos de la
;;; expresión e, pero usando el procedimiento mapcar. Por ejemplo,
;;;     (linealiza-map ())              =>  ()
;;;     (linealiza-map 'a)              =>  (a)
;;;     (linealiza-map '((a b) (c d)))  =>  (a b c d)

(defun linealiza-map (l)
       (cond ((null l) ())
             ((atom l) (list l))
             (t (apply 'append (mapcar 'linealiza-map l)))))

========================================================================

;;;;; REV_T.LL
;;;;; El procedimiento reverse-total
;;;;; Basado en Abelson [90] p. 99

;;;; Ejercicio 1 (Abelson [90] p. 99):
;;; Definir el procedimiento
;;;     (reverse-total l)
;;; que invierta la lista l y lo mismo con sus elementos. Por
;;; ejemplo,
;;;     (reverse-total '((a b) (c d)))  =>  ((d c) (b a))
;;;     (reverse-total 'a)              =>  a

(defun reverse-total (l)
       (cond ((null l) ())
             ((atom l) l)
             (t (append (reverse-total (cdr l))
                        (list (reverse-total (car l)))))))

;;;; Ejercicio 2:
;;; Definir el procedimiento
;;;     (reverse-total-map l)
;;; que invierta la lista l y lo mismo con sus elementos, pero
;;; usando el procedimiento mapcar. Por
;;; ejemplo,
;;;     (reverse-total-map '((a b) (c d)))  =>  ((d c) (b a))
;;;     (reverse-total-map 'a)              =>  a

(defun reverse-total-map (l)
       (cond ((null l) ())
             ((atom l) l)
             (t (reverse (mapcar 'reverse-total-map l)))))

========================================================================

;;;;; SUBST.LL
;;;;; Los procedimientos subst y subst-total
;;;;; Basado en Chailloux [86] p. 3-51

;;; que devuelva la lista obtenida sustituyendo en la expresión e
;;; todas las ocurrencias de la expresión v por la expresión n. Por
;;; ejemplo,
;;;     (subst 'a 'b '(a b (b) c))  =>  (a a (a) c)
;;;     (subst 'a 'b 'b)            =>  a
;;;     (subst '(a) 'b 'b)          =>  (a)

(defun subst (n v e)
       (cond ((equal e v) n)
             ((atom e) e)
             (t (cons (subst n v (car e))
                      (subst n v (cdr e))))))

;;;; Ejercicio 2:
;;; Definir el procedimiento
;;;     (subst-map n v e)
;;; que sea la versión aplicativa del procedimiento subst.

(defun subst-map (n v e)
       (cond ((equal e v) n)
             ((atom e) e)
             (t (mapcar '(lambda (x) (subst n v x))
                        e))))