LPP Tema2 - Apuntes 2 PDF

Preview

Summary

Apuntes del tema 2 tomados en clase y completados con la página de la asignatura...

Description

LPP – Tema 2 ->Quote: Si recibe una expresión correcta de Scheme (una expresión entre paréntesis) se devuelva la lista o pareja definida por la expresión (sin evaluar sus elementos).

'(1 2 3) ; ⇒ (1 2 3) Una lista '(+ 1 2 3 4) ; La lista formada por el símbolo + y los números 1 2 3 4 (quote (1 2 3 4)) ; La lista formada por los números 1 2 3 4 '(a b c) ; ⇒ La lista con los símbolos a, b, y c '(* (+ 1 (+ 2 3)) 5) ; Una lista con 3 elementos, el segundo de ellos otra lista '(1 . 2) ; ⇒ La pareja (1 . 2) '((1 . 2) (2 . 3)) ; ⇒ Una lista con las parejas (1 . 2) y (2 . 3)

->Listas: Se pueden crear listas de forma dinámica llamando a list y pasándole un número variables de parámetros que son los elementos que se incluirán en la lista: (list (list (list (list

1 2 3 4 5) ; ⇒ (1 2 3 4) 'a 'b 'c) ; ⇒ (a b c) 1 'a 2 'b 3 'c #t) ; ⇒ (1 a 2 b 3 c #t) 1 (+ 1 1) (* 2 (+ 1 2))) ; ⇒ (1 2 6)

En las listas sí se evalua el contenido. Mediante las funciones car y cdr podemos obtener elementos de una lista: -Con car sacamos el primer elemento de la lista, es decir, el de la izquierda: (define lista1 '(1 2 3 4)) (car lista1) ; ⇒ 1

-Con cdr sacamos el segundo elemento de la lista, es decir, el de la derecha (cdr lista1) ; ⇒ (2 3 4)

->Podemos componer listas con las funciones cons y append, que crean nuevas listas como resultado de juntar de otras. -Cons crea una lista nueva resultante de añadir un elemento al comienzo de la lista: (cons 1 '(1 2 3 4)) ; ⇒ (1 1 2 3 4) (cons 'hola '(como estás)) ; ⇒ (hola como estás) (cons '(1 2) '(1 2 3 4)) ; ⇒ ((1 2) 1 2 3 4)

-Append crea una lista nueva resultante de concatenar dos o más listas: (define list1 '(1 2 3 4)) (define list2 '(hola como estás)) (append list1 list2) ; ⇒ (1 2 3 4 hola como estás)

->Recursión •

Función (suma-hasta x)

1º Poner un ejemplo (suma-hasta 4) = 0+1+2+3+4=10 ---> Hay que llamar a la función recursiva dejando un problema más pequeño, es decir, 4+(suma-hasta 3) =10 (define (suma-hasta x) (if (= 0 x) 0 (+ (suma-hasta (- x 1)) x)))

En una definición recursiva siempre tenemos un caso general (el que llama a la recursión) y un caso base (el que para la recursión). •

Función (alfabeto-hasta char)

1º Poner un ejemplo (alfabeto-hasta #\h) = “abcdefgh” --> “h” +(alfabeto-hasta #\g) (define (anterior char) (integer->char (- (char->integer char) 1))) (define (alfabeto-hasta char) (if (equal? char #\a) "a" (string-append (alfabeto-hasta (anterior char)) (string char))))

•

Función (suma-lista lista)

1º Poner un ejemplo (suma-lista ‘(1 3 5 8)) =1+3+5+8=17 ---> 8+(suma-lista ‘(1 3 5)) (define (suma-lista lista) (if (null? lista) 0 (+ (car lista) (suma-lista (cdr lista)))))

•

Función (longitud lista)

1º Poner un ejemplo (longitud ’(1 2 3 4 5)) =5 (define (longitud lista) (if (null? lista) 0 (+ (longitud (cdr lista)) 1)))

•

Función (veces lista id)

1º Poner un ejemplo (veces ‘(a b c d e a f q w a) ‘a )=3 (define (veces lista id) (cond ((null? lista) 0) ((equal? (car lista) id) (+ 1 (veces (cdr lista) id))) (else (veces (cdr lista) id))))

->Tipos de datos compuestos en Scheme •

El tipo de dato pareja

(cons 1 2) ; ⇒ (1 . 2) (define c (cons 1 2))

-Las parejas pueden contener cualquier tipo de dato -Son inmutables -Son objetos de primera clase ■Pueden ser asignados a variables (1) (define p1 (cons 1 2)) ■Se pueden pasar como y argumentos y pueden ser devueltas como resultado de una función (2 y 3) (define p1 (cons 1 2)) (define p2 (cons 3 4)) (suma-parejas p1 p2) = (4 . 6) (define (suma-parejas p1 p2) (cons (+ (car p1) (car p2)) (+ (cdr p1) (cdr p2))))

■Pueden formar parte de otras parejas (4) (define p1 (cons 1 2)) (define p2 (cons 3 4)) (define p (cons p1 p2))

(define p (cons (cons 1 (cons 3 4)) 2))

->Listas en Scheme •

Similitud entre listas y parejas: 1. Una pareja formada por dos números es una pareja, pero no una lista (define p1 (cons 1 2)) (pair? p1) ; ⇒ #t (list? p1) ; ⇒ #f

2. Una lista vacía es una lista, pero no una pareja (list? '()) ; ⇒ #t (pair? '()) ; ⇒ #f

3. Una lista es una pareja (define lista '(1 2 3)) (list? lista) ; ⇒ #t (pair? lista) ; ⇒ #t

4. Una pareja, formada con una lista vacía como segundo elemento es una pareja y una lista (define p1 (cons 1 '())) (pair? p1) ; ⇒ #t (list? p1) ; ⇒ #t

•

Definición de listas con parejas

Una lista es una pareja que contiene en su parte izquierda el primer elemento de la lista y en su parte derecha el resto de la lista. ‘() denota la lista vacía (cons 1 '())

->Funciones de alto nivel sobre listas (append '(a (b) c) '((d) e f)) ; ⇒ (a (b) c (d) e f) (list-ref '(a (b) c d) 2) ; ⇒ c (length '(a (b (c))) ; ⇒ 2 (reverse '(a b c)) ; ⇒ (c b a) (list-tail '(a b c d) 2) ; ⇒ (c d)

•

Función mi-list-ref

1º Poner un ejemplo (mi-list-ref ‘(a b c d e ) 4) =e (define (mi-list-ref lista n) (if (= n 0) (car lista) (mi-list-ref (cdr lista) (- n 1))))

•

Función mi-list-tail

1º Poner un ejemplo (mi-list-tail ‘(1 2 3 4 5 6) 2) = ‘(3 4 5 6) (define (mi-list-tail lista n) (if (= n 0) lista (mi-list-tail (cdr lista) (- n 1))))

•

Función mi-append

1º Poner un ejemplo (mi-append ‘(a b c) ‘(d e f)) = (a b c d e f) (define (mi-append l1 l2) (if (null? l1) l2 (cons (car l1) (mi-append (cdr l1) l2))))

•

Función mi-reverse

1º Poner un ejemplo (mi-reverse ‘( 1 2 3 4 5 6)) =(6 5 4 3 2 1) (define (mi-reverse lista) (if (null? lista) '() (añade-al-final (car lista) (mi-reverse (cdr lista)))))

•

Función (cuadrados-hasta x)

(define (cuadrados-hasta x) (if (= x 1) '(1) (cons (cuadrado x) (cuadrados-hasta (- x 1)))))

•

Función (filtra-pares lista)

(define (filtra-pares lista) (cond ((null? lista) '()) ((even? (car lista)) (cons (car lista) (filtra-pares (cdr lista)))) (else (filtra-pares (cdr lista)))))

•

Función (primo? x)

(define (primo? x) (= 2 (length (divisores x)))) (define (divisores x) (filtra-divisores (lista-hasta x) x)) (define (filtra-divisores lista x) (cond ((null? lista) '()) ((divisor? (car lista) x) (cons (car lista) (filtra-divisores (cdr lista) x))) (else (filtra-divisores (cdr lista) x)))) (define (divisor? x y) (= 0 (mod y x))) (define (lista-hasta x) (if (= x 0) '() (cons x (lista-hasta (- x 1)))))

->Funciones con un número variable de argumentos Para poder pasar un número variable de argumentos se utiliza la notación punto-cola, en los que los parámetros antes del punto serán obligatorios establecerlos, y los que se encuentren detrás de la coma, pueden no estar. (define (funcion-dos-o-mas-args x y . lista-args) ) (funcion-dos-o-mas-args 1 2 3 4 5 6)

En este ejemplo, las variables x e y toman los valores 1 y 2, y lista-args, forma una lista con el resto de argumentos, es decir, con ‘( 3 4 5 6). (define (funcion-cualquier-numero-args . lista-args) ) (funcion-cualquier-numero-args 1 2 3 4 5 6)

En este caso, lista-args formará una lista con ‘(1 2 3 4 5 6). Esto se consigue no poniendo argumentos antes del punto, haciendo que todos sean opcionales. •

Función (mi-suma x y . lista-nums)

(define (mi-suma x y . lista-nums) (if (null? lista-nums) (+ x y) (+ x (+ y (suma-lista lista-nums)))))

->Forma especial lambda Esta función nos permite crear funciones anónimas en tiempo de ejecución. (lambda ( ... ) )

Ejemplo: Función anónima que suma dos parejas: (lambda (p1 p2) (cons (+ (car p1) (car p2)) (+ (cdr p1) (cdr p2))))

Ejemplo: Función anónima que devuelve el mayor de dos números. (lambda (a b) (if (> a b) a b))

Si ejecutamos una expresión lambda en el intérprete, este nos devuelve un procedimiento (lambda (x) (* x x)) ; ⇒ #

Este procedimiento devuelve el cuadrado de un número. Se le puede asignar un identificador mediante un define -> (define f (lambda (x) (* x x)))

Y este trabaja de la misma manera que esta definición -> (define x (+ 2 3))

La diferencia está en la llamada que hagamos en el intérprete: f ; ⇒ # x ; ⇒ 5

Para poder utilizar f, hay que invocarlo con un parámetro -> (f 3) ; ⇒ 9

No es necesario asignar un identificador a la función anónima, esta también puede ser invocada desde el intérprete de la siguiente forma: ((lambda (x) (* x x)) 3) ; ⇒ 9 ((lambda (x) (* x x)) 3) = (# 3) ⇒ 9

La forma especial define, no es más que azúcar sintáctico ya que al definir una función, lo que realmente hace Scheme es lo siguiente: (define ( ) ) (define (lambda () ))

Ejemplo: (define (cuadrado x) (* x x) (define cuadrado (lambda (x) (* x x))) ->Funciones como argumentos de otras funciones •

Función (aplica func x y)

Devuelve el resultado de aplicar la función que se la pasa como parámetro a los argumentos x e y. ->Generalización Se puede evitar repetir código de distintas formas, una de ellas es la generalización. Vamos a ver un ejemplo de ella. Supongamos la función (sumatorio-desde-a-hasta-b a b). Esta presente el siguiente cuerpo (define (sum-x a b) (if (> a b) 0 (+ a (sum-x (+ a 1) b))))

Sin embargo, ahora queremos hacer el sumatorio desde a hasta b, pero con los cuadrados de los números. En este caso tendría este cuerpo: (define (sum-cuadrado-x a b) (if (> a b) 0 (+ (* a a) (sum-cuadrado-x (+ a 1) b))))

También se podría aplicar para cualquier exponente. Pero para evitar repetir código podemos hacer como hemos hecho en la función aplica, definir previamente una función de lo que queramos. De esta forma, el cuerpo de la función será el siguiente: (define (sum-f-x f a b) (if (> a b) 0 (+ (f a) (sum-f-x f (+ a 1) b))))

Y para calcular el sumatorio desde a hasta b de los cubos, simplemente tendríamos que hacer lo siguiente: (define (cubo x) (* x x x))

Y en el interprete llamar a la función de forma (suma-f-x cubo a b). Utilizando expresiones lambda podemos generalizar para cualquier función: (suma-f-x (lambda(n) (/ n (- n 2))) a b) ->Funciones que devuelven funciones -Aquellas funciones que devuelven funciones se llaman constructoras. -Aquellas funciones que son devueltas por otras funciones se llaman clausuras. Función anónima creada en tiempo de ejecución. •

Función sumador

(define (construye-sumador k) (lambda (x) (+ x k)))

Cuando se invoca a construye-sumador se evalúa la expresión lambda y se devuelve el procedimiento creado. Ejemplo: (construye-sumador 10) = # Cuando se invoca a la función si darle valor al parámetro landa, el argumento k, toma el valor 10 por declararla en el ámbito local de la función. Posteriormente si se evalúa lambda se obtiene como resultado la suma de k + x ((construye-sumador 10) 3) =13 Otro ejemplo puede ser: (define g (construye-sumador 100))

(g 3) =103 •

Función composición

(define (composicion f g) (lambda (x) (f (g x))))

Primero se invoca a g, y el resultado se pasa a f. Ejemplo: (suponiendo que tenemos definidas las funciones doble y cuadrado) (define h (composicion doble cuadrado))

(h 4) =32 ->Funciones en estructuras de datos Podemos crear una lista de funciones que previamente han sido definidas

(define (cuadrado x) (* x x)) (define (suma-1 x) (+ x 1)) (define (doble x) (* x 2)) (define lista (list cuadrado suma-1 doble))

Para poder invocar una de las funciones, hay que utilizar las expresiones car y list-ref. ->Funciones que trabajan con listas de funciones •

Función (aplica-funcs lista-funcs x)

Recibe una lista de funciones en lista-funcs, que son aplicadas de derecha a izquierda al parámetro x. (define lista (list cuadrado cubo suma-1)) (define (aplica-funcs lista-funcs x) (if (null? lista-funcs) x ((car lista-funcs) (aplica-funcs (cdr lista-funcs) x)))) (aplica-funcs lista-funcs 5) ; ⇒ 46656

->Funciones de orden superior Son aquellas funciones que toman otras funciones como parámetro o devuelven una función. •

Función map:

-Transforma aplicando a todos sus elementos una función de transformación que se pasa como parámetro. Esta función puede recibir un número variable de argumentos (transforma elemento) -> elemento (map cuadrado '(1 2 3 4 5)) ; ⇒ (1 4 9 16 25) (define (mi-map f lista) (if (null? lista) '() (cons (f (car lista)) (mi-map f (cdr lista)))))

•

Función filter:

-Toma como parámetro un predicado y una lista, y devuelve como resultado los elementos de la lista que cumplen el predicado (filter even? '(1 2 3 4 5 6 7 8)) ; ⇒ (2 4 6 8) (filter (lambda (pareja) (>= (car pareja) (cdr pareja))) '((10 . 4) (2 . 4) (8 . 8) (10 . 20))) ; ⇒ ((10 . 4) (8 . 8)

(define (mi-filter pred lista) (cond ((null? lista) '()) ((pred (car lista)) (cons (car lista) (mi-filter pred (cdr lista)))) (else (mi-filter pred (cdr lista)))))

•

Función exists?

-Esta función recibe un predicado y una lista y comprueba si hay algún elemento de la lista que cumpla ese predicado. (define (exists? predicado lista) (if (null? lista) #f (or (predicado (car lista)) (exists? predicado (cdr lista))))) (exists? even? '(1 2 3 4 5 6)) ; ⇒ #t (exists? (lambda (x) (> x 10)) '(1 3 5 8)) ; ⇒ #f

•

Función for-all?

-Esta función recibe un predicado y una lista y comprueba que todos los elementos de la lista cumplan ese predicado. (define (for-all? predicado lista) (or (null? lista) (and (predicado (car lista)) (for-all? predicado (cdr lista)))))

•

Función foldr

-Esta función permite recorrer una lista aplicando una función binaria de forma acumulativa a sus elementos y devolviendo un único valor como resultado. (foldr combina base lista) (combina dato resultado) -> resultado

La función combina se aplica de derecha a izquierda, empezando por el último elemento de la lista y el valor inicial base. (define (suma dato resultado) (+ dato resultado))

El parámetro dato se va a coger de la lista y el segundo va a ser calculado (foldr suma 0 '(1 2 3)) ; ⇒ 6

La primera vez, se aplicará la función suma sobre el último elemento de la lista y el dato, en este caso 0, lo que dará 3. La siguiente operación será ((3+0) +2) =5 Y por último ((3+0) +2) +1) =6 Ejemplo: (foldr string-append "****" '("hola" "que" "tal")) ; ⇒ "holaquetal****"

(string-append "tal" "****") ; ⇒ "tal****" (string-append "que" "tal****") ; ⇒ "quetal****" (string-append "hola" "quetal****") ; ⇒ "holaquetal****"

•

Función foldl

-Esta función actúa igual que foldr, pero empezando por el primer elemento de la lista, es decir va de izquierda a derecha...