===== Problemario del taller de Haskell ===== ==== Funciones Simples ===== * Definir una función //entre0y9.n//, //entre0y9 : Int -> Bool// que, dado un entero, devuelve //True// si el entero se encuentra entre 0 y 9. probar con 0, 3, 5 y 9 * Definir una función //rangoEdad.x//, //rangoEdad : Int -> String// que dado un número //x// que representa la edad de una persona, retorne "joven" si la persona es menor de 35, "adulto" si la persona es menor de 65 pero mayor de 35, y "mayor" si la persona es mayor de 65. probar con 20, 35, 40, 65, 70 y -30. * Definir una función //segundo3.(x,y,z)//, //segundo3 : (Int,Int,Int) -> Int//, que dada una tresupla de enteros devuelve su segundo elemento. probar con (0,8,2) y con (3,3,3). * Definir una función //mayor3.(x,y,z)//, //mayor3 : (Int,Int,Int) -> (Bool,Bool,Bool)//, que, dada una una tresupla de enteros, devuelve una tresupla de booleanos que indica si cada uno de los enteros es mayor que 3. Por ejemplo: //mayor3.(1,4,3) -> (False,True,False)// ; //mayor3.(5,1984,6) -> (True,True,True)//. probar con (1,2,3), (-5,8,73490), (3,3,3). * Definir una función //ordena.(x,y)//, //ordena : (Int,Int) -> (Int,Int)// que, dados dos enteros, los ordena de menor a mayor. probar con (0,1), (2,2), (3,1). * Definir una función //ambospositivos.x.y//, //ambospositivos : Int -> Int -> Bool//, que dados dos enteros devuelve //True// si los dos son positivos. probar con 5 y 9, con -8 y 9, con -10 y -1, con 0 y 0 y con 0 y 3 * Definir una función //averaver.(x,y,z)//, //averaver : (Int,Int,Int) -> (Int,Int,Int)// que, dada una tresupla de enteros, si todos son positivos, invierte su orden, si todos son negativos, los cambia a positivos, y en cualquier otro caso, devuelve la misma tresupla. Ayuda: usar //otherwise//. probar con (1,2,3), (-1,-2,-3), (1,1,1), (-1,2,-3). * Definir una función //rangoPrecio.x//, //rangoPrecio : Int -> String// que dado un número //x// que representa el precio de una computadora, retorne "muy barato" si el precio es menor a 2000, "demasiado caro" si el precio es mayor que 5000, "hay que verlo bien" si el precio está entre 2000 y 5000, y "esto no puede ser!" si //x// es negativo. probar con 1523, 2000, 5000, 5001, -3000, 2001 y 1999 * Definir una función //absoluto.x//, //absoluto : Int -> Int// que dado un entero //x//, retorne su valor absoluto. probar con 3, -5 y 0. * Definir una función //signo.x//, //signo : Int -> Int// que dado un entero //x//, retorne su signo, de la siguiente forma: retornará 1 si //x// es positivo, -1 si es negativo y 0 en cualquier otro caso. probar con -8, 3 y 0. * Definir la función //esMultiplo2.n//, //esMultiplo2 : Int -> Bool// que dado un entero //n// devuelve //True// si //n// es múltiplo de 2. Ayuda: usar //'mod'//, el operador que devuelve el resto de la división. probar con 2, 0 y 5. * Definir una función //rangoPrecioParametrizado.x.(menor,mayor)//, //rangoPrecioParametrizado : Int -> (Int,Int) -> String// que dado un número //x// que representa el precio de un producto, un par //(menor,mayor)// que represente el rango de precios que uno espera encontrar, retorne "muy barato" si //x// está por debajo del rango, "demasiado caro" si está por arriba del rango, "hay que verlo bien" si el precio está en el rango, y "esto no puede ser!" si //x// es negativo. probar con 50 (30,200), 30 (30,200), -40 (200,1000), 50 (200,30), 200 (30,200), 201 (30,200). * Definir la función //esMultiplo.n.m//, //esMultiplo : Int -> Int -> Bool// que dado un entero //n// devuelve //True// si //n// es múltiplo de //m//. probar con 2 y 2, 0 y 3, 3 y 0 y 5 y 3. * Definir la función //cabeza.xs//, //cabeza : [a] --> a//, que devuelve el primer elemento de una lista. probar con [1,2,3], con [3,3,3] y con []. * Definir la función //cola.xs//, //cola : [a] --> [a]//, que devuelve toda la lista menos el primer elemento. probar con [1,2,3], con [3,3,3] y con []. * Definir una función //esVaciaOPrimer0.xs//, //esVaciaOPrimer0 : [a] -> Bool// que dada una lista //xs// decida si //xs// es vacía o bien su primer elemento es 0. probar con [1,2,3], con [3,3,3], con [0], con [0,1] y con []. === Un poco más complicadas... === * Definir el predicado //bisiesto : Int → Bool// que determina si un año es bisiesto. Recordar que los años bisiestos son aquellos que son divisibles por 4 pero no por 100, a menos que también lo sean por 400. Por ejemplo 1900 no es bisiesto pero 2000 sí lo es. probar con 1984, 1985, 1900 y 2000. * Definir la función //edad// con los siguientes tipos //edad : (Int, Int, Int) -> (Int, Int, Int) -> Int// que, dadas dos fechas, indica los años transcurridos entre ellas. Por ejemplo //edad.(20, 10, 1968).(30, 4, 1987) = 18//. Suponer que las fechas son correctas (no puede ser que aparezca un //(32,15,1999)//) y el primer argumento es menor que el segundo. probar con (16,4,1980) y (17,5,1992), (16,4,1980) y (14,5,1992), y con (16,4,1980) y (15,4,1992). === Para usar Definiciones Locales === * Completar la función //area.h.b.d// //area : Int -> Int -> Int -> Int// que calcula el área de un prisma rectangular: area.h.b.d = 2*frente + 2*lado + 2*tapa where frente = ... lado = ... tapa = ... donde //h// es su altura, //b// es su ancho y //d// su profundidad, y donde //frente//, //lado// y //tapa// son las áreas de las caras frontal, lateral y superior, respectivamente. * Completar la función //raices.a.b.c// //raices : Float -> Float -> Float -> (Float,Float)// que calcula las raíces de un binomio (problema 2.25 del [[http://www.lcc.uma.es/~pepeg/pfHaskell/codigo/cap02.hs|capítulo 2]] del [[http://www.lcc.uma.es/~pepeg/pfHaskell/codigo.htm|problemario de Pepe Gallardo]]) raices a b c | disc >= 0 = ((-b+raizDisc)/denom,(-b-raizDisc)/denom) | otherwise = error "raices complejas" where disc = ... raizDisc = ... denom = ... === Divide y Conquista === Suponer el siguiente juego: //m// jugadores en ronda comienzan a decir los números naturales consecutivamente. Cuando toca un multiplo de 7 o un número con algún dígito igual a 7, el jugador debe decir //pip// en lugar del número. \\ Se pide: encontrar un predicado //pip.n//, //pip : Int -> Bool// que dado un número //0%%<=%%n<10000// devuelva diga cuando el jugador debe decir //pip//. \\ Para hacerlo habrá que definir previamente las siguientes funciones: //unidad,decena,centena,unidadDeMil : Int -> Int//. ==== Funciones Simples ===== * Definir una función //entre0y9.n//, //entre0y9 : Int -> Bool// que, dado un entero, devuelve //True// si el entero se encuentra entre 0 y 9. probar con 0, 3, 5 y 9 * Definir una función //rangoEdad.x//, //rangoEdad : Int -> String// que dado un número //x// que representa la edad de una persona, retorne "joven" si la persona es menor de 35, "adulto" si la persona es menor de 65 pero mayor de 35, y "mayor" si la persona es mayor de 65. probar con 20, 35, 40, 65, 70 y -30. * Definir una función //segundo3.(x,y,z)//, //segundo3 : (Int,Int,Int) -> Int//, que dada una tresupla de enteros devuelve su segundo elemento. probar con (0,8,2) y con (3,3,3). * Definir una función //mayor3.(x,y,z)//, //mayor3 : (Int,Int,Int) -> (Bool,Bool,Bool)//, que, dada una una tresupla de enteros, devuelve una tresupla de booleanos que indica si cada uno de los enteros es mayor que 3. Por ejemplo: //mayor3.(1,4,3) -> (False,True,False)// ; //mayor3.(5,1984,6) -> (True,True,True)//. probar con (1,2,3), (-5,8,73490), (3,3,3). * Definir una función //ordena.(x,y)//, //ordena : (Int,Int) -> (Int,Int)// que, dados dos enteros, los ordena de menor a mayor. probar con (0,1), (2,2), (3,1). * Definir una función //ambospositivos.x.y//, //ambospositivos : Int -> Int -> Bool//, que dados dos enteros devuelve //True// si los dos son positivos. probar con 5 y 9, con -8 y 9, con -10 y -1, con 0 y 0 y con 0 y 3 * Definir una función //averaver.(x,y,z)//, //averaver : (Int,Int,Int) -> (Int,Int,Int)// que, dada una tresupla de enteros, si todos son positivos, invierte su orden, si todos son negativos, los cambia a positivos, y en cualquier otro caso, devuelve la misma tresupla. Ayuda: usar //otherwise//. probar con (1,2,3), (-1,-2,-3), (1,1,1), (-1,2,-3). * Definir una función //rangoPrecio.x//, //rangoPrecio : Int -> String// que dado un número //x// que representa el precio de una computadora, retorne "muy barato" si el precio es menor a 2000, "demasiado caro" si el precio es mayor que 5000, "hay que verlo bien" si el precio está entre 2000 y 5000, y "esto no puede ser!" si //x// es negativo. probar con 1523, 2000, 5000, 5001, -3000, 2001 y 1999 * Definir una función //absoluto.x//, //absoluto : Int -> Int// que dado un entero //x//, retorne su valor absoluto. probar con 3, -5 y 0. * Definir una función //signo.x//, //signo : Int -> Int// que dado un entero //x//, retorne su signo, de la siguiente forma: retornará 1 si //x// es positivo, -1 si es negativo y 0 en cualquier otro caso. probar con -8, 3 y 0. * Definir la función //esMultiplo2.n//, //esMultiplo2 : Int -> Bool// que dado un entero //n// devuelve //True// si //n// es múltiplo de 2. Ayuda: usar //'mod'//, el operador que devuelve el resto de la división. probar con 2, 0 y 5. * Definir una función //rangoPrecioParametrizado.x.(menor,mayor)//, //rangoPrecioParametrizado : Int -> (Int,Int) -> String// que dado un número //x// que representa el precio de un producto, un par //(menor,mayor)// que represente el rango de precios que uno espera encontrar, retorne "muy barato" si //x// está por debajo del rango, "demasiado caro" si está por arriba del rango, "hay que verlo bien" si el precio está en el rango, y "esto no puede ser!" si //x// es negativo. probar con 50 (30,200), 30 (30,200), -40 (200,1000), 50 (200,30), 200 (30,200), 201 (30,200). * Definir la función //esMultiplo.n.m//, //esMultiplo : Int -> Int -> Bool// que dado un entero //n// devuelve //True// si //n// es múltiplo de //m//. probar con 2 y 2, 0 y 3, 3 y 0 y 5 y 3. * Definir la función //cabeza.xs//, //cabeza : [a] --> a//, que devuelve el primer elemento de una lista. probar con [1,2,3], con [3,3,3] y con []. * Definir la función //cola.xs//, //cola : [a] --> [a]//, que devuelve toda la lista menos el primer elemento. probar con [1,2,3], con [3,3,3] y con []. * Definir una función //esVaciaOPrimer0.xs//, //esVaciaOPrimer0 : [a] -> Bool// que dada una lista //xs// decida si //xs// es vacía o bien su primer elemento es 0. probar con [1,2,3], con [3,3,3], con [0], con [0,1] y con []. === Un poco más complicadas... === * Definir el predicado //bisiesto : Int → Bool// que determina si un año es bisiesto. Recordar que los años bisiestos son aquellos que son divisibles por 4 pero no por 100, a menos que también lo sean por 400. Por ejemplo 1900 no es bisiesto pero 2000 sí lo es. probar con 1984, 1985, 1900 y 2000. * Definir la función //edad// con los siguientes tipos //edad : (Int, Int, Int) -> (Int, Int, Int) -> Int// que, dadas dos fechas, indica los años transcurridos entre ellas. Por ejemplo //edad.(20, 10, 1968).(30, 4, 1987) = 18//. Suponer que las fechas son correctas (no puede ser que aparezca un //(32,15,1999)//) y el primer argumento es menor que el segundo. probar con (16,4,1980) y (17,5,1992), (16,4,1980) y (14,5,1992), y con (16,4,1980) y (15,4,1992). === Para usar Definiciones Locales === * Completar la función //area.h.b.d// //area : Int -> Int -> Int -> Int// que calcula el área de un prisma rectangular: area.h.b.d = 2*frente + 2*lado + 2*tapa where frente = ... lado = ... tapa = ... donde //h// es su altura, //b// es su ancho y //d// su profundidad, y donde //frente//, //lado// y //tapa// son las áreas de las caras frontal, lateral y superior, respectivamente. * Completar la función //raices.a.b.c// //raices : Float -> Float -> Float -> (Float,Float)// que calcula las raíces de un binomio (problema 2.25 del [[http://www.lcc.uma.es/~pepeg/pfHaskell/codigo/cap02.hs|capítulo 2]] del [[http://www.lcc.uma.es/~pepeg/pfHaskell/codigo.htm|problemario de Pepe Gallardo]]) raices a b c | disc >= 0 = ((-b+raizDisc)/denom,(-b-raizDisc)/denom) | otherwise = error "raices complejas" where disc = ... raizDisc = ... denom = ... === Divide y Conquista === Suponer el siguiente juego: //m// jugadores en ronda comienzan a decir los números naturales consecutivamente. Cuando toca un multiplo de 7 o un número con algún dígito igual a 7, el jugador debe decir //pip// en lugar del número. \\ Se pide: encontrar un predicado //pip.n//, //pip : Int -> Bool// que dado un número //0%%<=%%n<10000// devuelva diga cuando el jugador debe decir //pip//. \\ Para hacerlo habrá que definir previamente las siguientes funciones: //unidad,decena,centena,unidadDeMil : Int -> Int//. ==== Recursivos lineales ==== === Aplicación === * Definir la función //duplicar.xs//, //duplicar : [Int] -> [Int]// que dada una lista de enteros duplica cada uno de sus elementos. Ejemplo: //duplicar.[3,0,-2] = [6,0,-4]//. probar con [3,2,1], con [0,1,2] y con []. * Generalizar la función anterior definiendo //multiplicar.n.xs//, //multiplicar : Int -> [Int] -> [Int]// que dada un número //n// y una lista, multiplica cada uno de los elementos por //n//. Ejemplo: //multiplicar.3.[3,0,-2] = [9,0,-6]//. ?Cómo podemos definir //duplicar// a partir de //multiplicar//? probar con 1 [3,2,1], 10 [3,2,1], 0 [0,1,2] y [] 3. * Definir la función //esMultiploLista.n.xs//, //esMultiploLista : Int -> [Int] -> [Bool]// que dado un entero //n// y una lista de enteros //xs// devuelve una lista de booleanos que indica si //n// es múltiplo de cada uno de los elementos de la lista //xs//. Ejemplo: //esMultiploLista.6.[2,3,5] = [True,True,False]//. Otro ejemplo: //esMultiploLista.18.[4,2,3,6,8] = [False,True,True,True,False]//. === Acumulación === * Definir la función //longitud.xs//, //longitud : [Int] -> Int// que dada una lista de enteros computa su largo. Ejemplo: //longitud.[3,0,-2] = 3//. probar con [3,2,1], con [0,1,2] y con []. * Definir la función //sumatoria.xs//, //sumatoria : [Int] -> Int// que dada una lista devuelve la suma de sus elementos. probar con [1,2,3,4], [0,1,2,3,4], [0], [3,2,1], [3,2,1,1], [3,2,1,1,1], [3,2,1,1,1,1], [-8,3,2], []. * Definir la función //productoria.xs//, //productoria : [Int] -> Int// que dada una lista devuelve el producto de sus elementos. probar con [1,2,3,4], [0,1,2,3,4], [0], [3,2,1], [3,2,1,1], [3,2,1,1,1], [3,2,1,1,1,1], [-8,3,2], []. * Definir la función //sumaPares.xs//, //sumaPares : [(Int, Int)] -> Int//, que dada una lista de pares de números, devuelve la sumatoria de todos los números de todos los pares. Ejemplo: //sumaPares.[(1,2)(7,8)(11,0)] = 29//. (ejemplo 2.16 del problemario de Pepe Gallardo). probar con [(1,1)], [] y [(2,1),(1,2)]. * Definir la función //concatenaInt.xss//, //concatenaInt : [ [Int] ] -> [Int]// que dada una lista de enteros //xss// devuelve la concatenación de sus elementos. Ejemplo: //concatenaInt.[ [0,1],[],[2,3] ] = [0,1,2,3 // probar con [ [], [0,1,2], [] ], [ [] ], [ [1,2], [3,4] ] y ["hola","chau"]. * Definir la función //todos0y1.xs//, //todos0y1 : [Int] -> Bool// que dada una lista devuelve //True// si ésta consiste sólo de 0s y 1s. probar con [0], [], [1], [0,0,0,0], [0,1,0,1], [1,2,3], ['a','b','c'] * Definir la función //todosA.xs//, //todosA : [Char] -> Bool// que dada una lista devuelve //True// si ésta consiste sólo de letras A. probar con ['A','A','A'], ['a','A'], [], ['a','b','c','d'], ['A','B','C','D'], [1,'a',2]. * Definir la función //todosMenores10.xs//, //todosMenores10 : [Int] -> Bool// que dada una lista devuelve //True// si ésta consiste sólo de números menores que 10. probar con [0,1,2], [-3,-5], [], [0,1,2,10], [30,5]. * Definir la función //hay0.xs//, //hay0 : [Int] -> Bool// que dada una lista //xs// decide la existencia de algún 0. Ejemplo //hay0.[1,2] = False//, //hay0.[1,4,0,5] = True//. probar con [], [0,0,0,0], [1,2,3,4], [0] y [1,5,7,0,9] === Filtros === * Definir la función //soloPares.xs//, //soloPares : [Int] -> [Int]// que dada una lista de enteros //xs// devuelve una lista con los números pares contenidos en //xs//, en el mismo orden y con las mismas repeticiones (si las hubiera). probar con [0,1,2,3,4,5], [3,5,7], [2,4,6], [2,2,3,2,4], []. * Definir la función //quitar0s.xs//, //quitar0s : [Int] -> [Int]// que dada una lista de enteros //xs// devuelve una la lista pero quitando todos los ceros. Ejemplo //quitar0s [2,0,3,4] = [2,3,4]// probar con [0,0,0,0], [1,1,1,1], [], [0,0,0,1], [1,0,0,0]. * Generalizar //soloPares// definiendo //soloMultiplos.n.xs//, //soloMultiplos : Int -> [Int] -> [Int]// que dada una lista de enteros //xs// devuelve una lista con los números múltiplos de //n// contenidos en //xs//, en el mismo orden y con las mismas repeticiones (si las hubiera). Ayuda: usar la misma estrategia que para la función //esMultiplo.n.m//. probar con 2 [0,1,2,3,4,5], 3 [3,5,7], 4 [2,4,6], 0 [2,2,3,2,4], 2 []. === Misceláneas === * Definir la función //desdeHasta.n.m//, //desdeHasta : Int -> Int -> [Int]//, que retorna la lista de todos los enteros entre //n// y //m//. Ayuda, pensarlo primero para //n//%%<=%%//m// y luego extenderlo para que también acepte listas descendentes cuando //n>m//. probar con 2 y 10, con 3 y 3, con 0 y 5 y con 4 y 2. * Definir la función //ultimo.xs//, //ultimo : [a] -> a//, que devuelve el último elemento de una lista. probar con [0,1,2], con [2,1,0], con [1] y con []. * Definir la función //inicio.xs//, //inicio : [a] -> a//, que devuelve todos los elementos de la lista menos el último. probar con [0,1,2], con [2,1,0], con [1] y con []. * Definir la función //repetir.n.x//, //repetir : Int -> Int -> [Int]//, que una lista con //x// repetido //n// veces. Ejemplo //repetir.3.1 = [1,1,1]//. probar con 0 0, 0 10, 10 0, (-1) 5, 5 (-1). * Definir la función //reversa.xs//, //reversa : [Int] -> [Int]//, que devuelve la lista "espejada". Ejemplo //reversa.[1,2,3] = [3,2,1]//. probar con [1], [], [1,1,1], (desdeHasta.0.9999), (repetir.42.1) * Definir la función //ordenada.xs//, //ordenada : [Int] -> Bool//, que decide si la lista //xs// está ordenada de menor a mayor. Ejemplo //ordenada.[1,2,3,2] = False//. Ayuda: cuidado con **los** casos base. probar con [], [1], [1,2], [1,2,3], (desdeHasta.0.9999)++[0]. * Definir //aBinario : Int -> [Int]//, donde //aBinario.n// retorna la representación binaria de //n// como lista de bits, donde el primer elemento es el **bit menos significativo**. Ejemplo: //aBinario.18 = [0,1,0,0,1]//. probar con 0, 2, 170. * Definir la función inversa de //aBinario//. Entonces //deBinario : [Int] -> Int//, donde //deBinario.xs// retorna el decimal que representa la secuencia binaria, donde también tenemos el bit menos significativo al principio. Ejemplo: //deBinario.[0,1,0,0,1] = 18 // probar con [], [0], [0,0,0], [0,1], [0,1,0,1,0,1,0,1] * A partir de la [[http://es.wikipedia.org/wiki/Serie_de_Taylor | Serie de Taylor]] es posible aproximar la base de los logaritmos naturales o neperianos "[[http://es.wikipedia.org/wiki/N%C3%BAmero_e | e]]". \\ Definir la función //numeroE//, //numeroE : Integer -> Double//, donde //numeroE.n// retorna la sumatoria //1/0! + 1/1! + 1/2! + ... 1/n!//. Ejemplo: //numeroE.10 = 2.71828180114638//. \\ Probar como se pueden ir obteniendo todas los dígitos, comparar con el [[http://antwrp.gsfc.nasa.gov/htmltest/gifcity/e.1mil | primer millón de dígitos]]. ==== Generalizando los recursivos ==== Los siguientes ejercicios permiten generalizar algunas funciones que hemos visto hasta ahora, de forma que podemos escribir una sola función que, sólo cambiando un parámetro, haga lo que antes hacían muchas funciones distintas. === Aplicaciones (map) === * Definir la función //mapNumero.f.xs//, //mapNumero : (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: //mapNumero.(+2).[0,1,2,3] = [2,3,4,5]//. probar con mapNumeros.(*2).[0,1,2,3], mapNumeros.absoluto.[-10,0,10]. * Definir la función //mapNumeroString.f.xs//, //mapNumeroStrint : (Int -> String) -> [Int] -> [String]// que dada una función //f// que mapea enteros en cadenas y una lista de enteros //xs//, aplica //f// a cada elemento de //xs//. Ejemplo: //mapNumeroString.rangoEdad.[20,36,17,73] = ["joven","adulto","joven", "mayor"]//. probar con mapNumeroString.rangoPrecio.[1000,2000,3000,4000,5000,6000,7000] * 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//. probar con mapa.ordena.[(1,0)(0,1)], mapa.segundo3.[(10,20,30),(12,22,32),(14,24,34)], mapa.longitud.[[],[1],[1,2]], mapa.(\x -> [x,x])."tartamuda". PREGUNTA: ¿Qué función del preámbulo de Haskell es un mapa genérico? === Filtros (filter) === * Definir la función //filtraNumeros.p.xs//, //filtraNumeros : (Int -> Bool) -> [Int] -> [Int]// que dado 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 función //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]. * Generalice la función anterior para listas de cualquier tipo. Defina //filtro.f.xs//, //filtro : (a -> Bool) -> [a] -> [a]// que dado un predicado //f// 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 //f//. 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]. PREGUNTA: qué función del preámbulo de Haskell es un filtro genérico? === Acumuladores (fold) === * Definir la función //concatena.xss// que generaliza //concatenaPalabras//, //concatena: [ [a] ] -> [a]//, que dada una lista de lista xss retorna la concatenación (++) de los elementos de la lista. Ejemplo //concatena.[ [1,2], [3,4], [5] ] = [1,2,3,4,5]//. probar con concatena.[ [],[],[] ], concatena.[ [], [True], [] ], concatena.[]. * Definir la función //paraTodoInt.p.xs//, //paraTodoInt : (Int->Bool) -> [Int] -> Bool//, que dado un predicado //p// retorna verdader si y solo si, el predicado es válido para todos los elementos de la lista. Ejemplo //paraTodoInt.multiplo2.[2,4,6] = True//. probar con paraTodoInt.multiplo2.[2,3,4], paraTodoInt.entre0y9.[1,2,4,2,1], paraTodoInt.multiplo2.[]. * 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]. * Definir la función //acumulaBool.f.z.xs//, //acumulaBool : (Bool->Bool->Bool) -> Bool -> [Bool] -> Bool//, que dado un operador booleano //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: //acumulaBool.&&.True.[True,False,True] = False//. probar con acumulaBool.(||).False.(map entre0y9 [10,20,30,2,40]). * 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. PREGUNTA: ¿Qué funciones del preámbulo de Haskell son los acumuladores genéricos? ¿Por qué hay 2? ==== Recursivos en dos argumentos ==== * Definir //iguales : [Int] -> [Int] -> Bool//, donde //iguales.xs.ys// decide si las listas son iguales elemento a elemento. Ejemplo //iguales.[].[0,1] = False//, //iguales.[1,2].[1,2] = True//. probar con [] [10], [10] [], [9,10] [9,11], (desdeHasta.10.10000) (desdeHasta.10.9999). Pregunta: ¿Cuál es el compara genérico del preámbulo? * Definir //cerrar2 : [Int] -> [Int] -> [(Int,Int)]//, donde //cerrar2.xs.ys// devuelve una lista donde cada elemento es un par formado a partir de las dos listas. Ejemplo //cerrar2 [0,1,2] [10,20,30] = [(0,10), (1,20), (2,30)]//. probar con [] [], [1] [1], [] [1,2,3], [1,2,3] [], [4] [4,5,6]. Pregunta: ¿Cuál es el cerrar2 genérico del preámbulo? * Definir //tomar :: Int -> [Int] -> [Int]//, donde //tomar.n.xs// devuelve hasta los primeros //n// elementos de //xs//. Ejemplo //tomar.2.[0,1,2,3] = [0,1]//. probar con 2 [0,1], 2 [0], 2 [], 0 [], 0 [0,1,2], (-1) [0,1,2]. Pregunta: ¿Cuál es el tomar genérico del preámbulo? * Definir //tirar :: Int -> [Int] -> [Int]//, donde //tirar.n.xs// devuelve hasta los primeros //n// elementos de //xs//. Ejemplo //tirar.2.[0,1,2,3] = [2,3]//. probar con 2 [0,1], 2 [0], 2 [], 0 [], 0 [0,1,2], (-1) [0,1,2]. Pregunta: ¿Cuál es el tirar genérico del preámbulo? * Definir //nEsimo :: Int -> [Int] -> Int//, donde //nEsimo.n.xs// devuelve el //n//-esimo elemento de //xs//. Ejemplo //nEsimo.2.[0,1,2,3] = 2//. probar con 2 [0,1], 2 [0], 2 [], 0 [], 0 [0,1,2], (-1) [0,1,2]. Pregunta: ¿Cuál es el nEsimo genérico del preámbulo? * Defina //mezclaOrdenada :: [Int] -> [Int] -> [Int]//, donde //mezclaOrdenada.xs.ys// devuelve la mezcla ordenada a partir de las dos listas **ordenadas** //xs// y //ys//. Ejemplo //mezclaOrdenada.[0,2,4,6].[1,3,5] = [0,1,2,3,4,5,6]//. Ayuda: piense en como procedería con 2 mazos de cartas. probar con [] [1,2,3], [1,2,3] [], [1,2,3] [4,5,6], [4,5,6] [1,2,3], [0,1,2,5] [3,4], [1,2,3] [1,2,3], [] [], [3,4] [0,1,2,5]. ==== Para componer ==== * Definir la función //capicua : [Int] -> Bool //, donde //capicua.xs// decide si la lista es [[http://es.wikipedia.org/wiki/Capic%C3%BAa|capicúa]]. Utilizar la función //reversa// e //iguales//. * Escribir una definición alternativa de //hay0// usando //filtro// y //longitud//. * Redefinir //duplicar// y //multiplicar// con **//map//**. * Redefinir //sumatoria//, //soloPares// y //hay0// utilizando **//acumular//**. * Escribir una definición de //paraTodo// utilizando **//acumular//**. * Escribir //factorial// utilizando //desdeHasta// y **//acumular//**. * Definir la función //insertaOrd : Int -> [Int] -> [Int]//, donde //insertaOrd.x.xs// inserta de manera ordenada el elemento //x// dentro de la lista //xs// que suponemos ordenada de menor a mayor. A partir de esta función definir //ordenaIns : [Int] -> [Int]// que ordena los elementos de una lista de menor a mayor. * Definir la función //partir : [Int] -> ([Int],[Int])// que divide una lista en dos partes iguales. A partir de esta definición y de //mezclaOrdenada//, definir //ordenaMez : [Int] -> [Int]// que ordena los elementos de una lista de menor a mayor. * Redefinir //ordenada// a partir de //ordenaIns// u //ordenaMez// e //iguales//. * A partir de //ordenaIns// u //ordenaMez//, definir la función //permutacion : [Int] -> [Int] -> Bool// que decide si una lista es permutación de la otra. * Definir la función //primo : Int -> Bool// a partir de //esMultiplo//, //desdeHasta//, //iguales// y //filtro// la cual decide sobre la primalidad de un número, utilizando el hecho de que un número primo //p// tiene por divisores //[1,p]//. * Definir la función //primosHasta: Int -> [Int]//, donde //primosHasta.n// retorna la lista de todos los primos contenidos en el rango //[1,n]//. * Definir la función //edadReal: [(String,String,Int,Bool)] -> [(String,Int)]//, que toma una lista de cuatruplas con la siguiente información sobre personas: nombre de la persona, sexo, edad y si está mintiendo en la edad o no, y devuelve una lista de tuplas con el nombre y la edad de cada persona, de forma que si es una mujer que miente sobre su edad (tiene "True" en el cuarto elemento de la cuatrupla) se le suma 5 a la edad de la cuatrupla, y si es un hombre, se le resta 5. Ejemplo: edadReal [ ("Ana","M",45,False), ("Pedro","H",30,False), ("Teresa","M",35,True), ("Esteban","H",40,False) ] = [ ("Ana",45), ("Pedro",30), ("Teresa",45), ("Esteban",35) ] * Definir la función //escalaImpuesto: [(String,Int)] -> [(String,Int)]//, que toma una lista de tuplas con el nombre de un usuario y su gasto mensual de electricidad, y devuelve una lista de tuplas con el nombre de aquellos usuarios que gastan más de 50 pesos mensuales de electricidad y su gasto multiplicado por 3. Esta función se puede usar para recalcular el impuesto a pagar por los usuarios que más gastan. Ejemplo: escalaImpuesto [("Perez",30), ("Gomez",67), ("Martinez",55), ("Rodriguez",24)] = [("Gomez",201),("Rodriguez",72)] * 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. ==== Para lucirse ==== * Definir //potencia2 : Int -> Int// que calcula 2n utilizando sólo recursión y sumas. * Definir //trianguloPascal : Int -> [Int]//, donde //trianguloPascal.n// retorna las //n// primeras filas del [[http://es.wikipedia.org/wiki/Tri%C3%A1ngulo_de_Pascal|Triángulo de Pascal]]. Por ejemplo //trianguloPascal.4 = [ [1], [1,1], [1,2,1], [1,3,3,1] ]//. * Definir //ordenaQuick :: [Int] -> [Int]// que ordena una lista utilizando la idea de [[http://es.wikipedia.org/wiki/Quicksort | Quicksort]] de [[http://es.wikipedia.org/wiki/C._A._R._Hoare | Tony Hoare]]. * Definir //criba : [Int]// que retorna la lista (infinita) de los números primos a partir del método de la [[http://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes|Criba de Eratóstenes]]. * Reescribir utilizando //acumula// las funciones: //iguales//, //map//, //filtro// y //reverse//. Observación: estos ejercicios no son especialmente difíciles pero requieren un grado de abstracción importante. * Definir //permutaciones : [a] -> [ [a] ]// que retorna la lista de todas las permutaciones de una lista. * **Redefinir** la función escalaImpuesto: [(String,Int)] → [(String,Int)], que toma una lista de tuplas con el nombre de un usuario y su gasto mensual de electricidad, y devuelve una lista de tuplas con el nombre de aquellos usuarios que gastan más de **la media** de electricidad y su gasto multiplicado por la diferencia entre su gasto y el gasto medio. * La función //numeroE// puede ser extremadamente ineficiente para valores elevados de //n//, debido a que por cada sumando computa nuevamente el factorial. Generalizar la función de manera que tome un parámetro más y en ese se lleve el factorial que le corresponde a ese término. Comparar la eficiencia en término del tiempo.