| Ambos lados, revisión anteriorRevisión previaPróxima revisión | Revisión previa |
| introalg:problemas07 [2007/04/16 16:14] – Errorcitos nicolasw | introalg:problemas07 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1 |
|---|
| |
| ===== Problemario del taller de Haskell ===== | ===== Problemario del taller de Haskell ===== |
| | |
| |
| |
| 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//. \\ | 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//. | Para hacerlo habrá que definir previamente las siguientes funciones: //unidad,decena,centena,unidadDeMil : Int -> Int//. |
| | |
| | |
| |
| |
| probar con [(1,1)], [] y [(2,1),(1,2)]. | 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 // | * 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"]. | 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. | * 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], [0,0,0], [0,1], [0,1,0,1,0,1,0,1] | 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 ==== | ==== Generalizando los recursivos ==== |
| probar con mapNumeroString.rangoPrecio.[1000,2000,3000,4000,5000,6000,7000] | probar con mapNumeroString.rangoPrecio.[1000,2000,3000,4000,5000,6000,7000] |
| |
| * Generalizar //mapNumero// y //mapNumeroString// con //map.f.xs//, //map : (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//. | * 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 map.ordena.[(1,0)(0,1)], map.segundo3.[(10,20,30),(12,22,32),(14,24,34)], | probar con mapa.ordena.[(1,0)(0,1)], mapa.segundo3.[(10,20,30),(12,22,32),(14,24,34)], |
| map.longitud.[[],[1],[1,2]], map.(\x -> [x,x])."tartamuda". | mapa.longitud.[[],[1],[1,2]], mapa.(\x -> [x,x])."tartamuda". |
| |
| PREGUNTA: qué función del preámbulo de Haskell es un map genérico? | PREGUNTA: ¿Qué función del preámbulo de Haskell es un mapa genérico? |
| |
| |
| === Filtros (filter) === | === Filtros (filter) === |
| |
| * Definir la función //filtraNumeros.f.xs//, //filtraNumeros : (Int -> Bool) -> [Int] -> [Int]// que dada un predicado //f// 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 //f//. Ejemplo: //filtraNumeros.entre0y9.[11,4,37,3,10] = [4,3]//. Un ejemplo con algunas implicaciones más: //filtraNumeros.(esMultiplo.3).[1,2,3,4,5,6,7,8,9,10] = [3,6,9]//. | * 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]. | 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//. | * 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 acumulaBool.(||).False.(map entre0y9 [10,20,30,2,40]). | 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->a) -> a -> [b] -> a//, que dado un operador binario //f// (asociativo a izquierda), un elemento //z// neutro (a izquierda) 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"//. | * 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. | 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? | PREGUNTA: ¿Qué funciones del preámbulo de Haskell son los acumuladores genéricos? ¿Por qué hay 2? |
| | |
| | |
| | |
| | |
| |
| ==== Recursivos en dos argumentos ==== | ==== Recursivos en dos argumentos ==== |
| probar con [] [10], [10] [], [9,10] [9,11], (desdeHasta.10.10000) (desdeHasta.10.9999). | 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? | Pregunta: ¿Cuál es el compara genérico del preámbulo? |
| |
| |
| probar con [] [], [1] [1], [] [1,2,3], [1,2,3] [], [4] [4,5,6]. | 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? | Pregunta: ¿Cuál es el cerrar2 genérico del preámbulo? |
| |
| |
| probar con 2 [0,1], 2 [0], 2 [], 0 [], 0 [0,1,2], (-1) [0,1,2]. | 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? | Pregunta: ¿Cuál es el tomar genérico del preámbulo? |
| |
| |
| probar con 2 [0,1], 2 [0], 2 [], 0 [], 0 [0,1,2], (-1) [0,1,2]. | 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? | Pregunta: ¿Cuál es el tirar genérico del preámbulo? |
| |
| |
| probar con 2 [0,1], 2 [0], 2 [], 0 [], 0 [0,1,2], (-1) [0,1,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? | 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. | * 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], | 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]. | [0,1,2,5] [3,4], [1,2,3] [1,2,3], [] [], [3,4] [0,1,2,5]. |
| |
| |
| |
| |
| |
| ==== Para componer ==== | ==== Para componer ==== |
| |
| * Definir la función //capicua : [Int] -> Bool //, donde //capicua.xs// decide si la lista es capicúa. Utilizar la función //reversa//. | * 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//. | * Escribir una definición alternativa de //hay0// usando //filtro// y //longitud//. |
| * Redefinir //sumatoria//, //soloPares// y //hay0// utilizando **//acumular//**. | * Redefinir //sumatoria//, //soloPares// y //hay0// utilizando **//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. A partir de esta función definir //ordenaIns : [Int] -> [Int]// que ordena los elementos de una lista de menor a mayor. | * 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. | * 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. | * 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//, //paraTodoInt//, la cual decide sobre la primalidad de un número. | * 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 //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 //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]]. | * 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 //acumular// las funciones: //iguales//, //map//, //filtro// y //reverse//. | * 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. | * 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. |
