Diferencias

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

--- introalg:taller08_4 [2008/05/08 00:34] – creado laura
+++ introalg:taller08_4 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
@@ Línea 7: / Línea 7: @@
 ===== Aplicación parcial (secciones) =====
-Tomemos la siguente función Haskell que es una ligera variación de //esMultiplo// que está en el problemario.
+Tomemos la siguente función Haskell que es una ligera variación de //esMultiplo// que está en el problemario: la función //esDivisor//, que toma dos enteros y devuelve True si el segundo es divisor del primero.
 <code>
@@ Línea 13: / Línea 13: @@
   esDivisor p n = n `mod` p == 0
 </code>
-La función //esDivisor// toma dos enteros y devuelve True si el segundo es divisor del primero.
 Ahora podemos usar la función //esDivisor// para definir la función //esPar//:
@@ Línea 30: / Línea 28: @@
 Por lo tanto, una función es un ciudadano de primera categoría en Haskell, puede ser devuelto como resultado de una función y también veremos que puede ser un parámetro de entrada.
-Gracias a esta forma de agruparse, podemos definir las funciones sin especificar sus argumentos, siempre que estos vengan dados por el contexto de forma inequívoca. Por ejemplo, veamos esta versión **sin argumentos** de la función //esPar//:
+Gracias a esta forma de agruparse, podemos definir las funciones sin especificar sus argumentos, siempre que estos vengan dados por el contexto de forma inequívoca. Por ejemplo, veamos esta versión de la función //esPar// donde no ha sido necesario escribir el argumento:
 <code>
@@ Línea 39: / Línea 37: @@
 Como se ve, en esta definición no hemos especificado el argumento //x//, que es al que se le aplican las funciones que estamos usando. No es necesario especificarlo porque en ambos casos se trata del único argumento que requiere la función.
-Esta forma de escribir funciones se denomina [[http://en.wikipedia.org/wiki/Currying|currificación]], en honor al lógico [[http://es.wikipedia.org/wiki/Haskell_Curry|Haskell Curry]] ((Si si, el lenguaje Haskell se llama así por Haskell Curry.)).
+Esta forma de escribir funciones se denomina [[http://en.wikipedia.org/wiki/Currying|currificación]], en honor al lógico [[http://es.wikipedia.org/wiki/Haskell_Curry|Haskell Curry]] ((Sí, sí, el lenguaje Haskell se llama así por Haskell Curry.)).
-Este mecanismo de aplicación parcial de argumentos, o secciones, resulta muy elegante para escribir funciones.
+Este mecanismo de aplicación parcial de argumentos, o secciones, proporciona una forma elegante de escribir funciones.
 Por ejemplo:
@@ Línea 50: / Línea 48: @@
 </code>
-O bien las usamos las secciones directamente en la función //map//:
+En esta definición de //incrementa//, está claro que el número al que se le va a sumar 1 es el que se dá como único argumento de la función.
+También podemos usar las secciones directamente en la función //map//:
   Main> map (+1) [2,3,4,5]
@@ Línea 60: / Línea 60: @@
   Main> map (esDivisor 2) [2,3,4,5]
   [True,False,True,False]
+En este caso, la función toma como argumento cada uno de los elementos de la lista sucesivamente.
 Tiene que quedar claro que esta es una forma **elegante** y **compacta** de definir nuevas funciones a partir de otras, pero no es imprescindible. Por ejemplo, para //map (==0)// podemos definir la función auxiliar
@@ Línea 73: / 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) ====
-==== Aplicaciones ====
 ¿No estamos ya cansados de escribir siempre lo mismo?
@@ Línea 123: / Línea 111: @@
 </code>
-Entonces **generalicemos** definiendo una función que toma como primer argumento la función que se aplicará a cada elemento de la lista.
+Entonces **generalicemos**. Vemos que todas las funciones son iguales excepto por la operación que se aplica a cada uno de los elementos de la lista. Entonces, podemos definir una función general para cualquier aplicación, donde la operación que se aplica a cada uno de los elementos de la lista viene dada como un argumento más de la función. Esto es, definimos una función (la función //aplicación//) que toma como parámetro a otra función (la operación que se aplica a cada elemento de la lista).
-Vemos nuevamente la aplicación del **alto orden**, un nombre muy pomposo para algo bastante natural: **las funciones son un tipo más que puede ser tomado como parámetro y devuelto como resultado**.
+Como ya hemos visto, esto es perfectamente posible en Haskell. Recibe el nombre de **alto orden**, un nombre muy pomposo para algo bastante natural: **las funciones son un tipo más que puede ser tomado como parámetro y devuelto como resultado**. Recordemos el ejemplo de divisor, que devolvía como resultado una función de tipo //Int -> Bool//.
-De nuevo, se dice que en Haskell las funciones son //ciudadanos de primera categoría//.
-Esto no ocurre en la mayoría de los //lenguajes imperativos// como C, C++, Pascal, Basic, etc. .
-Notar que ya vimos funciones que devuelven funciones! Por ejemplo.
   esDivisor :: Int -> (Int -> Bool)
   esDivisor 2 :: Int -> Bool
+La forma generalizada de las funciones de aplicación se compone de lo que tienen en común todas las funciones aplicación que hemos visto hasta ahora, tomamos la definición de la función //rangoEdades// y nos quedamos con la parte común a todas las aplicaciones:
-=== Ejercicio ===
+  rangoEdades :: [Int] -> [String]
+  rangoEdades []     = []
+  rangoEdades (x:xs) = rangoEdad x : rangoEdades xs
-  * 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]//.
+  ___________ :: [Int] -> [String]
+  ___________ []     = []
+  ___________ (x:xs) = _________ x : ___________ xs
-  probar con mapNumeros.(*2).[0,1,2,3], mapNumeros.absoluto.[-10,0,10].
+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]
+  ___________ []     = []
+  ___________ (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.
+  aplicar :: (a -> b) -> [a] -> [b]
+  aplicar f []     = []
+  aplicar f (x:xs) = f x : aplicar f xs
-==== Filtros ====
+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
+  cuadrados xs = aplicar (^2) xs
+  rangoEdades xs = aplicar rangoEdad xs
+O bien aplicando secciones, es decir, sin escribir los argumentos obvios:
+  duplicar = aplicar (*2)
+  cuadrados = aplicar (^2)
+  rangoEdades = aplicar rangoEdad
+==== Filtros (filter) ====
 Veamos funciones de //tipo filtro// que hemos creado:
@@ Línea 169: / Línea 178: @@
 </code>
-Entonces plantemos el mismo tipo de ejercicio, una generalización que tome como primer parámetro un **predicado**, es decir una función que devuelve un booleano, que decidirá si cada elemento se conserva o se filtra.
+¿Cuál es la estructura que tienen en común estas funciones?
-=== Ejercicio ===
+  __________ :: [Int] -> [Int]
+  __________ [] = []
+  __________ (x:xs) | ______ x  =  x : _____________ xs
+                    | otherwise =      _____________ xs
-  * 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]//.
-  probar con filtraNumeros.entre0y9.[], filtraNumeros.entre0y9.[10,20,30].
+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
+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.
+  filtrar :: (a -> Bool) -> [a] -> [a]
+  filtrar p []     = []
+  filtrar p (x:xs) | p x       = x : filtrar p xs
+                   | otherwise =     filtrar p xs
+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:
-==== Acumuladores ====
+  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 (foldr) ====
 Más y más funciones fueron acumuladores, veamos algunas:
@@ Línea 200: / Línea 233: @@
 productoria (x:xs) = producto x (productoria xs)
 </code>
 <code>
@@ Línea 208: / 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.