Post on 24-Aug-2020
Tema 3: Características de la programación funcional
Sesión 9: El paradigma funcional (5)
martes 8 de marzo de 2011
Hoy veremos
• Características de la programación funcional en LISP/Scheme
• Tema 4: Procedimientos y estructuras recursivas
martes 8 de marzo de 2011
list devuelve la primera pareja de la lista
• La construcción de una lista devuelve la primera pareja de la misma. Así, tras evaluar la expresión:
• La variable lista tomará el valor de la primera pareja de la lista, la pareja formada por un 1 y el resto de la lista. Es lo mismo que cuando hacemos:
• cons para formar una nueva lista
(define lista (list 1 2 3))
(define lista (cons 1 (cons 2 (cons 3 '()))))
> (define l1 '(1 2 3 4))> (cons 'hola l1)(hola 1 2 3 4)
martes 8 de marzo de 2011
Scheme muestra las estructuras compuestas como listas
• Cuando Scheme imprime una estructura compuesta por parejas, va recorriendo la estructura intentando escribirla como una lista. Por ejemplo:
• Esta última estructura no es una lista
> (cons 1 (cons 2 (cons 3 '())))(1 2 3)>(cons 1 (cons 2 3))(1 2 . 3)
martes 8 de marzo de 2011
Listas con elementos compuestos
• Las listas pueden contener cualquier tipo de elementos, incluyendo otras parejas.
• La siguiente estructura se denomina lista de asociación: una lista cuyos elementos son parejas:
• ¿Cuál sería el diagrama de la lista anterior?
• La expresión equivalente utilizando parejas:
(list (cons 'a 1) (cons 'b 2) (cons 'c 3)) -> ((a.1)(b.2)(c.2))
martes 8 de marzo de 2011
Listas con elementos compuestos
• Las listas pueden contener cualquier tipo de elementos, incluyendo otras parejas.
• La siguiente estructura se denomina lista de asociación: una lista cuyos elementos son parejas:
• ¿Cuál sería el diagrama de la lista anterior?
• La expresión equivalente utilizando parejas:
(list (cons 'a 1) (cons 'b 2) (cons 'c 3)) -> ((a.1)(b.2)(c.2))
(cons (cons 'a 1) (cons (cons 'b 2) (cons (cons 'c 3) '())))
martes 8 de marzo de 2011
Listas de listas
• Las listas, al igual que las parejas, pueden contener cualquier tipo de dato, incluso otras listas:
• La lista anterior también la podemos definir con quote:
• ¿Cuál sería su representación con parejas?
• ¿Y su diagrama caja y puntero?
(define l1 (list 1 2 3))(define l2 (list 1 l1 2 3))
(define l2 '(1 (1 2 3) 2 3))
martes 8 de marzo de 2011
Implementación de funciones sobre listas
• Implementa la función mi-append que reciba dos listas como argumento y devuelva una nueva lista compuesta por la concatenación de las dos listas recibidas.
martes 8 de marzo de 2011
Implementación de funciones sobre listas
• Implementa la función mi-append que reciba dos listas como argumento y devuelva una nueva lista compuesta por la concatenación de las dos listas recibidas.
(define (mi-append l1 l2) (if (null? l1) l2 (cons (car l1) (mi-append (cdr l1) l2))))
martes 8 de marzo de 2011
Implementación de funciones sobre listas
• Implementa la función mi-length que reciba una lista como argumento y devuelva el número de elementos que contiene (en el primer nivel).
> (mi-length '(1 2 3 (4 5 6)))4
martes 8 de marzo de 2011
Implementación de funciones sobre listas
• Implementa la función mi-length que reciba una lista como argumento y devuelva el número de elementos que contiene (en el primer nivel).
> (mi-length '(1 2 3 (4 5 6)))4
(define (mi-length items) (if (null? items) 0 (+ 1 (mi-length (cdr items)))))
martes 8 de marzo de 2011
Los datos compuestos pueden ser funciones
• Definimos la función mi-cons como:
• La función anterior es equivalente a la función cons de Scheme.
• Se devuelve un procedimiento que admite un argumento m (mensaje).
• Cuando al procedimiento se le pasa el mensaje 'car devolverá el argumento x original de mi-cons y cuando se le pasa el mensaje 'cdr devolverá el argumento y
(define (mi-cons x y) (lambda (m) (cond ((equal? m 'car) x) ((equal? m 'cdr) y) (else (error "mensaje no definido: " m)) )))
martes 8 de marzo de 2011
Los datos compuestos pueden ser funciones
• Definimos la función mi-cons como:
• ¿Cómo la utilizamos? Pensad en un ejemplo
(define (mi-cons x y) (lambda (m) (cond ((equal? m 'car) x) ((equal? m 'cdr) y) (else (error "mensaje no definido: " m)) )))
martes 8 de marzo de 2011
Los datos compuestos pueden ser funciones
• Definimos la función mi-cons como:
• ¿Cómo la utilizamos? Pensad en un ejemplo
(define (mi-cons x y) (lambda (m) (cond ((equal? m 'car) x) ((equal? m 'cdr) y) (else (error "mensaje no definido: " m)) )))
> (define p (mi-cons 'hola #f))> (p 'car)hola> (p 'cdr)#f
martes 8 de marzo de 2011
Los datos compuestos pueden ser funciones
• Definimos la función mi-cons como:
• Funciones
• Funciones que encapsulan la llamada a la función:
• Ahora no hay ninguna diferencia entre el comportamiento de las funciones originales y el de las nuestras
(define (mi-cons x y) (lambda (m) (cond ((equal? m 'car) x) ((equal? m 'cdr) y) (else (error "mensaje no definido: " m)) )))
martes 8 de marzo de 2011
Los datos compuestos pueden ser funciones
• Definimos la función mi-cons como:
• Funciones
• Funciones que encapsulan la llamada a la función:
• Ahora no hay ninguna diferencia entre el comportamiento de las funciones originales y el de las nuestras
(define (mi-cons x y) (lambda (m) (cond ((equal? m 'car) x) ((equal? m 'cdr) y) (else (error "mensaje no definido: " m)) )))
(define (mi-car pareja) (pareja 'car))
(define (mi-cdr pareja) (pareja 'cdr))
martes 8 de marzo de 2011
Los datos compuestos pueden ser funciones
• Definimos la función mi-cons como:
• Funciones
• Funciones que encapsulan la llamada a la función:
• Ahora no hay ninguna diferencia entre el comportamiento de las funciones originales y el de las nuestras
(define (mi-cons x y) (lambda (m) (cond ((equal? m 'car) x) ((equal? m 'cdr) y) (else (error "mensaje no definido: " m)) )))
(define (mi-car pareja) (pareja 'car))
(define (mi-cdr pareja) (pareja 'cdr))
(define p (mi-cons (mi-cons 1 (mi-cons 3 4)) 2))> (mi-car (mi-cdr (mi-car p)))3
martes 8 de marzo de 2011
Tema 4: Procedimientos y estructuras recursivas
Sesión 9: Recursión (1)
martes 8 de marzo de 2011
En este tema veremos...
• Diseño de procedimiento recursivos
• Recursión mutua
• Coste espacial de la recursión
• Recursión por la cola
• Expresiones S
• Árboles binarios y genéricos
martes 8 de marzo de 2011
Confía en la recursión
• Para diseñar procedimientos recursivos debemos fijarnos en lo que hace el procedimiento (programación declarativa):
• Debemos descomponer el problema de forma que podamos lanzar la recursión sobre una versión más sencilla del mismo
• Obtener la solución de la versión más pequeña
• Devolver la solución completa
• Debemos confiar en que la llamada recursiva va a hacer su trabajo y devolver el resultado correcto, sin preocuparnos de cómo lo va a hacer.
• Es útil utilizar una notación matemática antes de programar.
martes 8 de marzo de 2011
Longitud de una lista
• Definición matemática de la longitud de una lista:
• Implementación:
martes 8 de marzo de 2011
Longitud de una lista
• Definición matemática de la longitud de una lista:
• Implementación:
Longitud (l) = 1 + Longitud (resto (l)) Longitud (lista-vacía) = 0
martes 8 de marzo de 2011
Longitud de una lista
• Definición matemática de la longitud de una lista:
• Implementación:
Longitud (l) = 1 + Longitud (resto (l)) Longitud (lista-vacía) = 0
(define (mi-length items) (if (null? items) 0 (+ 1 (mi-length (cdr items)))))
martes 8 de marzo de 2011
Sumatorio
• Definición matemática del sumatorio:
• Implementación:
martes 8 de marzo de 2011
Sumatorio
• Definición matemática del sumatorio:
• Implementación:
Sumatorio(min,max) = min + Sumatorio (min+1, max) Sumatorio(min,max) = min si min=max
martes 8 de marzo de 2011
Sumatorio
• Definición matemática del sumatorio:
• Implementación:
Sumatorio(min,max) = min + Sumatorio (min+1, max) Sumatorio(min,max) = min si min=max
(define (sumatorio min max) (if (= min max) min (+ min (sumatorio (+ 1 min) max))))
martes 8 de marzo de 2011
list-reverse
• ¿Cómo podríamos de invertir una lista forma recursiva? Un minuto para confiar en la recursión
• Escribe la definición matemática
• Escribe el programa en Scheme
martes 8 de marzo de 2011
mi-list-ref
• Implementación:
martes 8 de marzo de 2011
mi-list-ref
• Implementación:
(define (mi-list-ref lista n) (cond ((null? lista) (error "indice mayor que tamaño de lista")) ((= n 0) (car lista)) (else (mi-list-ref (cdr lista) (- n 1)))))
martes 8 de marzo de 2011
Recursión mutua
• Hay veces en que la definición de una función se puede realizar en función de una segunda, que a su vez se define en base a la primera.
• Ejemplo:
• Programas en Scheme:
x es par si x-1 es imparx es impar si x-1 es par0 es par
martes 8 de marzo de 2011
Recursión mutua
• Hay veces en que la definición de una función se puede realizar en función de una segunda, que a su vez se define en base a la primera.
• Ejemplo:
• Programas en Scheme:
x es par si x-1 es imparx es impar si x-1 es par0 es par
(define (par? x) (if (= 0 x) #t (impar? (- x 1))))
martes 8 de marzo de 2011
Recursión mutua
• Hay veces en que la definición de una función se puede realizar en función de una segunda, que a su vez se define en base a la primera.
• Ejemplo:
• Programas en Scheme:
x es par si x-1 es imparx es impar si x-1 es par0 es par
(define (par? x) (if (= 0 x) #t (impar? (- x 1))))
(define (impar? x) (if (= 0 x) #f (par? (- x 1))))
martes 8 de marzo de 2011
Ejemplo avanzado: curvas de Hilbert
• La curva de Hilbert es una curva fractal que tiene la propiedad de rellenar completamente el espacio. Su dibujo tiene una formulación recursiva.
• Vemos que la curva H3 se puede construir a partir de la curva H2.
martes 8 de marzo de 2011
Ejemplo avanzado: curvas de Hilbert
• Utilizamos la librería graphics/turtles que permite usar la tortuga y comandos de Logo en Scheme (draw y turn).
• La función (h-der i w) dibuja una curva de Hilbert de orden i con una longitud de trazo w a la derecha de la tortuga.
• La función (h-izq i w) dibuja una curva de Hilbert de orden i con una longitud de trazo w a la izquierda de la tortuga.
martes 8 de marzo de 2011
Algoritmo curva de Hilbert
• Para dibujar una curva de Hilbert de orden i a la derecha de la tortuga:
• El algoritmo para dibujar a la izquierda es simétrico.
Gira la tortuga -90Dibuja una curva de orden i-1 a la izquierdaAvanza w dibujandoGira 90Dibuja una curva de orden i-1 a la derechaAvanza w dibujandoDibuja una curva de orden i-1 a la derechaGira 90Avanza w dibujandoDibuja una curva de orden i-1 a la izquierdaGira -90
martes 8 de marzo de 2011
Algoritmo en Scheme
(require graphics/turtles)(turtles #t)(define (h-der i w) (if (> i 0) (begin (turn -90) (h-izq (- i 1) w) (draw w) (turn 90) (h-der (- i 1) w) (draw w) (h-der (- i 1) w) (turn 90) (draw w) (h-izq (- i 1) w) (turn -90))))
(define (h-izq i w) (if (> i 0) (begin (turn 90) (h-der (- i 1) w) (draw w) (turn -90) (h-izq (- i 1) w) (draw w) (h-izq (- i 1) w) (turn -90) (draw w) (h-der (- i 1) w) (turn 90))))
martes 8 de marzo de 2011
Lo probamos
• Podemos probarlo con distintos parámetros de grado de curva y longitud de trazo:
• El resultado de esta última llamada es:
(clear)(h-izq 3 20)(h-izq 6 5)
martes 8 de marzo de 2011