| Ambos lados, revisión anteriorRevisión previaPróxima revisión | Revisión previa |
| introalg:taller07_3 [2007/04/20 21:13] – laura | introalg:taller07_3 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1 |
|---|
| factorial :: Int -> Int | factorial :: Int -> Int |
| factorial 0 = 1 -- caso base | factorial 0 = 1 -- caso base |
| factorial (n+1) = n * factorial (n-1) -- caso inductivo | factorial (n+1) = (n+1) * factorial n -- caso inductivo |
| </code> | </code> |
| |
| |
| <code> | <code> |
| fib n = fib (n-1) + fib (n-2) | fib (n+2) = fib (n+1) + fib n |
| </code> | </code> |
| |
| |
| Notar que en las funciones de tipo "map" toman siempre a una lista como argumento y devuelven una lista como resultado; la lista de resultado se obtiene de **concatenar** el resultado de aplicar una función dada a cada uno de los elementos de la lista argumento. | Notar que en las funciones de tipo "map" toman siempre a una lista como argumento y devuelven una lista como resultado; la lista de resultado se obtiene de **concatenar** el resultado de aplicar una función dada a cada uno de los elementos de la lista argumento. |
| | |
| |
| |
| [] | [] |
| |
| | ==== Múltiples casos base ==== |
| |
| ==== Con más de un caso base ==== | Recordemos que el número de casos base depende del problema concreto que estemos tratando. En la Sucesión de Fibonacci, encontramos dos casos base: fib 0 = 1 y fib 1 = 1. En la mayor parte de casos con listas tenemos un solo caso base, el de la lista vacía [], pero para algunos problemas podemos necesitar 2 o más casos base. Veamos por ejemplo la función //emparejar.xs//, //emparejar : [String] -> [(String,String)]//, que pone en parejas los elementos de una lista de strings que representen, por ejemplo, los nombres de los chicos de una clase, y nos devuelve una forma de agruparlos en parejas para, por ejemplo, distribuirlos en los asientos de un colectivo. |
| | |
| Recordemos que el número de casos base depende del problema concreto que estemos tratando. En la Sucesión de Fibonacci, encontramos dos casos base: fib 0 = 1 y fib 1 = 1. En la mayor parte de casos con listas tenemos un solo caso base, el de la lista vacía [], pero para algunos problemas podemos necesitar 2 o más casos base. Veamos por ejemplo la función //emparejar.xs//, //emparejar : [Int] -> [(Int,Int)]//, que pone en parejas los elementos de una lista de enteros. | |
| |
| <code> | <code> |
| emparejar :: [Int] -> [(Int,Int)] | emparejar :: [String] -> [(String,String)] |
| emparejar (x:y:xs) = (x,y) : emparejar xs | emparejar (x:y:xs) = (x,y) : emparejar xs |
| emparejar [x] = [(x,x)] | emparejar [x] = [(x,x)] |
| emparejar [] = [] | emparejar [] = [] |
| </code> | </code> |
| | |
| | Veamos cómo funciona. |
| | |
| | Main> emparejar ["Pepa","Lola","Juan","Pili","Pedro"] |
| | [("Pepa","Lola"),("Juan","Pili"),("Pedro","Pedro")] |
| | |
| |
| ===== Ejercicios ===== | ===== Ejercicios ===== |
| === Aplicar === | === Aplicar === |
| |
| * Definir la función //veintePorCiento.xs//, //veintePorCiento : [Int] -> [Float]// que dada una lista de enteros devuelve una lista con el 20% de cada elemento de la lista. | * Definir la función //veintePorCiento.xs//, //veintePorCiento : [Float] -> [Float]// que dada una lista de números devuelve una lista con el 20% de cada elemento de la lista. |
| |
| probar con [345,20,46,0], [] y [3]. | probar con [345,20,46,0], [] y [3]. |
| |
| * Generalizar la función //veintePorCiento// definiendo //porCiento.n.xs//, //porCiento : Int -> [Int] -> [Float]// que dado un número //n// y una lista, devuelve el //n// por ciento de cada uno de los elementos de la lista. Ejemplo: //porCiento 10 [200,87,6] = [20,8.7,0.6]// | * Generalizar la función //veintePorCiento// definiendo //porCiento.n.xs//, //porCiento : Int -> [Float] -> [Float]// que dado un número //n// y una lista, devuelve el //n// por ciento de cada uno de los elementos de la lista. Ejemplo: //porCiento 10 [200,87,6] = [20,8.7,0.6]//. Puede ser útil la función ''fromIntegral'' que transforma un ''Int'' en ''Float''. |
| |
| * Generalizar la función //duplicar// 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]//. | * Generalizar la función //duplicar// 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]//. |
| === Miscelánea === | === Miscelánea === |
| |
| * Escribir la función que calcula la Sucesión de Fibonacci, //fib.n//, //fib : Int -> Int//, que se define así: //fib(n) = fib(n-1) + fib(n-2)//. | * Escribir la función que calcula la Sucesión de Fibonacci, //fib.n//, //fib : Int -> Int//, que se define así: //fib (n+2) = fib (n+1) + fib n//. |
| |
| probar con 4, 3, 2, 1 y 0. | probar con 4, 3, 2, 1 y 0. |
| probar con [(1,1)], [] y [(2,1),(1,2)]. | probar con [(1,1)], [] y [(2,1),(1,2)]. |
| |
| * 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. Ayuda: para construir el Booleano del resultado no pueden usar el constructor de listas ":", sino que tienen que usar algún operador que dé como resultado un Booleano. |
| |
| probar con [0], [], [1], [0,0,0,0], [0,1,0,1], [1,2,3], ['a','b','c'] | probar con [0], [], [1], [0,0,0,0], [0,1,0,1], [1,2,3], ['a','b','c'] |
| |
| probar con [], [0,0,0,0], [1,2,3,4], [0] y [1,5,7,0,9] | probar con [], [0,0,0,0], [1,2,3,4], [0] y [1,5,7,0,9] |
| | |
| | * Definir la función //repetir.n.x//, //repetir : Int -> a -> [a]// que dado un elemento lo repite n veces, dando como resultado una lista que contiene las repeticiones. |
| | |
| | probar con 8 y "bobo", 0 y 33 y 4 y []. |
| |
| * 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]//. | * 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]//. |
