Diferencias

Muestra las diferencias entre dos versiones de la página.

--- introalg:taller08_4 [2008/05/10 22:57] – laura
+++ introalg:taller08_4 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
@@ Línea 75: / Línea 75: @@
   [False,False,False,False]
-=== Ejercicio ===
-  * Utilizando aplicación parcial en //( /= )//, definir la función //noEsCero :: Int -> Bool// que decide si un entero //x// es distinto a 0.
+===== Generalización de las funciones vistas (map, filter, fold) =====
+==== Aplicaciones (map) ====
-===== Generalización de las funciones vistas (map, filter, fold) =====
-==== Aplicaciones ====
 ¿No estamos ya cansados de escribir siempre lo mismo?
@@ Línea 128: / Línea 124: @@
   rangoEdades (x:xs) = rangoEdad x : rangoEdades xs
-              :: [Int] -> [String]
+  ___________ :: [Int] -> [String]
-              []     = []
+  ___________ []     = []
-              (x:xs) =           x :             xs
+  ___________ (x:xs) = _________ x : ___________ xs
 Si queremos hacer esta expresión independiente de tipos, usaremos los comodines de tipo //a//, //b//, etc. en lugar de los tipos comunes //Int//, //String//, etc.
-              :: [a] -> [b]
+  ___________ :: [a] -> [b]
-              []     = []
+  ___________ []     = []
-              (x:xs) =           x :             xs
+  ___________ (x:xs) = _________ x : ___________ xs
 A esta base común hay que añadir un argumento más: la función que se aplicará a todos los elementos de la lista. En el ejemplo anterior, la función era //rangoEdad//, pero en el caso generalizado no la vamos a especificar en la función sino que vamos a pedir que nos venga dada como un argumento más cuando se llama a la función.
@@ Línea 147: / Línea 143: @@
 De esta forma, llamando a la función general con diferentes operaciones como argumento, podremos definir las diferentes funciones que hemos visto hasta ahora, por ejemplo:
-duplicar xs = aplicar (*2) xs
+  duplicar xs = aplicar (*2) xs
-cuadrados xs = aplicar (^2) xs
+  cuadrados xs = aplicar (^2) xs
-rangoEdades xs = aplicar rangoEdad xs
+  rangoEdades xs = aplicar rangoEdad xs
 O bien aplicando secciones, es decir, sin escribir los argumentos obvios:
-duplicar = aplicar (*2)
+  duplicar = aplicar (*2)
-cuadrados = aplicar (^2)
+  cuadrados = aplicar (^2)
-rangoEdades = aplicar rangoEdad
+  rangoEdades = aplicar rangoEdad
-=== Ejercicio ===
+==== Filtros (filter) ====
-  * Definir la función //mapNumeros.f.xs//, //mapNumeros : (Int -> Int) -> [Int] -> [Int]// que dada una función //f// y una lista de enteros //xs//, les aplica una función aritmética //f// y concatena el resultado en una lista. Ejemplo: //mapNumeros.(+2).[0,1,2,3] = [2,3,4,5]//.
-  probar con mapNumeros.(*2).[0,1,2,3], mapNumeros.absoluto.[-10,0,10].
-==== Filtros ====
 Veamos funciones de //tipo filtro// que hemos creado:
@@ Línea 200: / Línea 186: @@
-A esta base común hay que añadir un argumento más: la función que se va a evaluar para todos los elementos de la lista. Este tipo de función es un **predicado**, es decir una función que devuelve un booleano, que decidirá si cada elemento se conserva o se filtra. En el ejemplo anterior, el predicado era primeraEsM, pero en el caso generalizado no lo vamos a especificar en la función sino que vamos a pedir que nos venga dado como un argumento más cuando se llama a la función.
+Si queremos hacer esta expresión independiente de tipos, usaremos los comodines de tipo a, b, etc. en lugar de los tipos comunes Int, String, etc.
+  __________ :: [a] -> [a]
+  __________ [] = []
+  __________ (x:xs) | ______ x  =  x : _____________ xs
+                    | otherwise =      _____________ xs
-=== Ejercicio ===
+A esta base común hay que añadir un argumento más: la función que se va a evaluar para todos los elementos de la lista. Este tipo de función es un **predicado**, es decir una función que devuelve un booleano, que decidirá si cada elemento se conserva o se filtra. En el ejemplo anterior, el predicado era primeraEsM, pero en el caso generalizado no lo vamos a especificar en la función sino que vamos a pedir que nos venga dado como un argumento más cuando se llama a la función.
-  * Definir la función //filtraNumeros.p.xs//, //filtraNumeros : (Int -> Bool) -> [Int] -> [Int]// que dada un predicado //p// y una lista de enteros //xs// devuelve la lista que contiene sólo aquellos números de //xs// que devuelven //True// en la predicado //p//. Ejemplo: //filtraNumeros.entre0y9.[11,4,37,3,10] = [4,3]//. Un ejemplo con algunas implicaciones más: //filtraNumeros.(esDivisor.3).[1,2,3,4,5,6,7,8,9,10] = [3,6,9]//.
+  filtrar :: (a -> Bool) -> [a] -> [a]
+  filtrar p []     = []
+  filtrar p (x:xs) | p x       = x : filtrar p xs
+                   | otherwise =     filtrar p xs
-  probar con filtraNumeros.entre0y9.[], filtraNumeros.entre0y9.[10,20,30].
+De esta forma, llamando a la función general con diferentes operaciones como argumento, podremos definir las diferentes funciones que hemos visto hasta ahora, por ejemplo:
+  soloPares xs = filtrar esPar xs
+  empiezaM xs = filtrar primeraEsM xs
+O bien aplicando secciones, es decir, sin escribir los argumentos obvios:
+  soloPares = filtrar esPar
+  empiezaM = filtrar primeraEsM
+Observemos que en el caso de los filtros, los elementos de la lista resultado tienen que ser del mismo tipo que los elementos de la lista que damos como argumento (//[a] -> [a]//), ya que la función filtro **no modifica** los elementos, sino que solamente determina si deben o no deben formar parte del resultado. En cambio, en las aplicaciones el resultado puede ser de distinto tipo que el argumento (//[a] -> [b]//), porque la aplicación sí puede modificar los elementos de la lista de entrada, incluso cambiándolos de tipo. Notemos que //[a] -> [b]// significa que **podemos** encontrar tipos distintos (como en //rangoEdad//) pero esto no es obligatorio: podemos encontrar que //a// y //b// representen el mismo tipo (como en //duplicar//).
-==== Acumuladores ====
+==== Acumuladores (foldr) ====
 Más y más funciones fueron acumuladores, veamos algunas:
@@ Línea 232: / Línea 233: @@
 productoria (x:xs) = producto x (productoria xs)
 </code>
 <code>
@@ Línea 240: / Línea 240: @@
 </code>
-=== Ejercicio ===
+¿Cuál es la estructura común de todas estas funciones? Para poder verla bien, debemos saber que todo operador que usemos entre sus dos argumentos, como //+//, //:// o //++//, se puede usar también con la misma sintaxis que cualquier otra función, es decir, delante de sus dos argumentos. Para ello hay que poner al operador entre paréntesis, como hemos visto en el último de los ejemplos de arriba con el operador //++//. De esta forma, el caso recursivo de la función sumatoria también se puede escribir así:
-Definir la primera generalización.
+  sumatoria (x:xs) = (+) x (sumatoria xs)
-  * Definir la función //paraTodoInt.p.xs//, //paraTodoInt : (Int->Bool) -> [Int] -> Bool//, que dado un predicado //p// retorna verdadero si y solo si, el predicado es válido para todos los elementos de la lista. Ejemplo //paraTodoInt.multiplo2.[2,4,6] = True//.
+Donde el primer número a sumar es //x// y el segundo es //sumatoria xs//, es decir, el resultado de resolver la función //sumatoria xs//.
-  probar con paraTodoInt.multiplo2.[2,3,4], paraTodoInt.entre0y9.[1,2,4,2,1], paraTodoInt.multiplo2.[].
+Entonces, la estructura común de todas estas funciones es:
-Y luego esta que es casi completa.
+  _________ :: [a] -> b
+  _________ []     = _____
+  _________ (x:xs) = _____ x (_________ xs)
-  * Definir la función //acumulaInt.f.z.xs//, //acumulaInt : (Int->Int->Int) -> Int -> [Int] -> Int//, que dado un operador //f//, un elemento //z// neutro del operador y una lista //xs//, retorna la acumulación del operador con //z// (cero) y con cada uno de los elementos de la lista. Ejemplo: //acumulaInt.max.0.[1,9,3,7,0] = 9//.
-  probar con acumulaInt.(+).0.[1,2,3], acumulaInt.(*).1.[1,2,3].
+Como el resultado de la función no es una lista, el resultado del caso base no es una lista vacía. El resultado del caso base debe ser definido para cada función, ya que debe ser el neutro del operador que se utilice en la función. Por lo tanto, en los acumuladores tendremos un argumento más que en las aplicaciones y los filtros, justamente, el neutro.
-===== Escribamos las versiones más generales =====
+Por lo tanto, la generalización de los acumuladores es la siguiente:
-Hasta ahora trabajamos con las generalizaciones de las funciones desde el punto de vista que le podíamos dar cualquier función para que operara sobre los valores.
+  acumular :: (a -> b -> b) -> b -> [a] -> b
-Es posible generalizar estas funciones a los **tipos**.
+  acumular f n []     = n
+  acumular f n (x:xs) =  f x (acumular f n xs)
-==== Aplicaciones (map) ====
+Ahora podemos escribir todas las funciones que son acumuladores mediante esta generalización.
-Si escribimos la definición de //mapNumeros// vemos que solo importa que la función //f// toma un elemento del tipo de la primer lista y genera un elemento del tipo de la segunda lista, luego podemos utilizar variables de tipo y definir la función:
+  sumatoria xs = acumular (+) 0 xs
+  productoria xs = acumular (*) 1 xs
+  concatenaInt xs = acumular (++) [] xs
-  * Generalizar //mapNumero// y //mapNumeroString// con //mapa.f.xs//, //mapa : (a -> b) -> [a] -> [b]// que dada una función que lleva algo de tipo //a// a tipo //b// y una lista //xs// de cualquier tipo //a// devuelve una lista //b// con el resultado de aplicar la función //f// a cada elemento de //xs//.
+O bien aplicando secciones, es decir, sin escribir los argumentos obvios:
-  probar con mapa.ordena.[(1,0)(0,1)], mapa.segundo3.[(10,20,30),(12,22,32),(14,24,34)],
+  sumatoria = acumular (+) 0
-    mapa.longitud.[[],[1],[1,2]], mapa.(\x -> [x,x])."tartamuda".
+  productoria = acumular (*) 1
+  concatenaInt = acumular (++) []
-La escribamos:
-<code>
+===== Ejercicios =====
-mapa :: (a -> b) -> [a] -> [b]
-mapa f []     =
-mapa f (x:xs) =
-</code>
+  * Escribir //duplicar// y //multiplicar// con //aplicar//.
-==== Filtros (filter) ====
-Lo mismo para //filtraNumeros// podemos filtrar los elementos de una lista de cualquier tipo:
-  * Generalice la función //filtraNumeros// para listas de cualquier tipo. Defina //filtro.f.xs//, //filtro : (a -> Bool) -> [a] -> [a]// que dado un predicado //p// y una lista //xs// de tipo //a//, devuelve una lista del mismo tipo que contiene sólo aquellos elementos de //xs// que son //True// en la función //p//.
-  probar con filtro.esMultiplo2.[1,2,3,4,5,6], filtro.(esMultiplo.3).[1,2,3,4,5,6,7,8,9,10],
-  filtro.(==0).[1,2,3,4].
-La escribamos:
-<code>
-filtro :: (a->Bool) -> [a] -> [a]
-filtro p []     =
-filtro p (x:xs) =
-</code>
-==== Acumuladores (fold) ====
-La generalización de los acumuladores a distintos tipos es un poco más complicada.
-Veamos la función de acumulación que dice si todos los elementos son 0 y 1.
-<code>
-todos0y1 :: [Int] -> Bool
-todos0y1 []     = True
-todos0y1 (x:xs) = (x==0 || x==1) && todos0y1 xs
-</code>
-Detectamos:
-  * Un "**cero**" respecto a la acumulación (//True// es neutro de la conjunción).
-  * Una función de acumulación que a partir del elemento actual y lo acumulado en la llamada recursiva sobre //xs//, obtiene el valor de lo acumulado en el total //x:xs//.
-Podemos reescribirla de la siguiente manera para que la función de acumulación sea más explícita.
-<code>
-ceroUnoYAnteriores :: Int -> Bool -> Bool
-ceroUnoYAnteriores x b = (x==0 || x==1) && b
-todos0y1' :: [Int] -> Bool
-todos0y1' []     = True
-todos0y1' (x:xs) = ceroUnoYAnteriores x (todos0y1' xs)
-</code>
-La defunición general sería:
-  * Generalice la función anterior para operadores y listas de cualquier tipo. Definir //acumula.f.z.xs//, //acumula : (a->b->b) -> b -> [a] -> b//, que dado un operador binario //f// (asociativo a derecha), un elemento //z// neutro (a derecha) del operador y una lista //xs//, retorna la acumulación del operador con //z// (cero) y con cada uno de los elementos de la lista. Ejemplo: //acumula.(++).[].["Hola", " ", "que", " ", "tal"] = "Hola que tal"//.
-  probar con todos los ejemplos de las versiones menos generales.
-Nuevamente la escribimos.
-<code>
-acumula :: (a->b->b) -> b -> [a] -> b
-acumula f z []     =
-acumula f z (x:xs) =
-</code>
-===== Reescribiendo funciones usando map, fold y filter =====
-==== Ejercicios ====
-  * Escribir //duplicar// y //multiplicar// con //mapa//.
     * Reescribir ambas utilizando aplicación parcial sobre //mapa// para evitar escribir el argumento de la lista.
-  * Utilizando //mapa// escribir la función //largos :: [String] -> [Int]// que dada una lista de cadenas, retorna la lista con la longitud de cada una.
+  * Utilizando //aplicar// escribir la función //largos :: [String] -> [Int]// que dada una lista de strings, retorna la lista con la longitud de cada una. //Ayuda: recordar que los strings son listas de caracteres.//
-  * Escribir //soloPares// y //quitar0s// con //filtro//.
+  * Escribir //soloPares// y //quitar0s// con //filtrar//.
-    * Reescribir ambas utilizando aplicación parcial sobre //mapa// para evitar escribir el argumento de la lista.
+    * Reescribir ambas utilizando aplicación parcial sobre //aplicar// para evitar escribir el argumento de la lista.
-  * Escribir //concatenaInt// usando //acumula//.
+  * Escribir //concatenaInt// usando //acumular//.
-  * Escribir //sumatoria// usando aplicación parcial con //acumula//.
+  * Escribir //sumatoria// usando aplicación parcial con //acumular//.
-  * Escribir //paraTodoInt// usando //acumula//.
+  * Escribir //paraTodoInt// usando //acumular//.
-  * Escribir //longitud// usando //acumula//.
+  * Escribir //longitud// usando //acumular//.
-  * Escribir //reversa// usando //acumula//.
+  * Escribir //reversa// usando //acumular//.
-  * **(DIFÍCIL)** Escribir //mapa// y //filtro// usando //acumula//.
+  * **(DIFÍCIL)** Escribir //aplicar// y //filtrar// usando //acumular//.
+  * Definir la función //cuantosCumplen//, //cuantosCumplen :: (Int -> Bool) -> [Int] -> Int//, que dado un predicado //p// y una lista de enteros //xs//, cuenta cuántos elementos de la lista cumplen con //p//.
+  * Definir la función //sumaPares//, //sumaPares :: [Int] -> Int//, que suma sólo los elementos pares de una lista.
+  * Definir la función //estudiantesMayores35//, //estudiantesMayores35 :: [(String,Int,Int,Int)] -> Int//, que dada una lista de cuatro-uplas //(String,Int,Int,Int)// que se corresponden con //(Nombre,Año-Nacimiento,Año-Inicio-Estudios,Año-Fin-Estudios)//, devuelve la cantidad de estudiantes que fueron mayores de 35 años en algún momento en el transcurso de sus estudios.
+  * Definir la función //listaMayorQue//, //listaMayorQue :: Int -> [ [ a ] ] -> Bool//, que dado un número //n// y una lista de listas, devuelve True si todas las listas de la lista tienen por lo menos //n// elementos.
+  * Definir la función //totalSueldos//, //totalSueldos :: [Int] -> Int//, que dada una lista con el monto de cada uno de los sueldos que paga una empresa, aplica una suba del 5% a todos los sueldos y devuelve el monto total que gastará la empresa en sueldos.
+  * Definir la función //impuestoLujo//, //impuestoLujo :: [(String,Int)] -> [(String,Int)]//, que dada una lista de tuplas //(Producto, Precio)//, aplica un impuesto del 21% extra a todos los productos que salen más de 10000 pesos.
+  * Definir la función //cuentaInteresantes//, //cuentaInteresantes :: [(String,Bool)] -> Int//, que cuenta la cantidad de libros interesant es que hay en una biblioteca. Los libros están representados mediante una tupla //(String, Bool)//, que contiene el título del libro en el primer elemento y en el segundo el elemento contiene True si el libro es interesante y False si no lo es.
+  * Definir la función //edadPromedio//, //edadPromedio:: [(String,Int)] -> Int//, que dada una lista de pares //(nombre,edad)//, retorna el promedio de edad de las personas.