| Ambos lados, revisión anteriorRevisión previaPróxima revisión | Revisión previa |
| introalg:taller07_3 [2007/04/20 19:35] – nicolasw | 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> |
| |
| [False,True,True,True,False] | [False,True,True,True,False] |
| </code> | </code> |
| | |
| |
| |
| duplicar (x:xs) = 2*x : duplicar xs -- caso inductivo | duplicar (x:xs) = 2*x : duplicar xs -- caso inductivo |
| </code> | </code> |
| | |
| | La probamos. |
| | |
| | Main> duplicar [10,20] |
| | [20,40] |
| | Main> duplicar [10,20,30] |
| | [20,40,60] |
| | Main> duplicar [1..10] |
| | [2,4,6,8,10,12,14,16,18,20] |
| | Main> duplicar [0..10] |
| | [0,2,4,6,8,10,12,14,16,18,20] |
| | |
| |
| 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. |
| | |
| | |
| | |
| |
| ==== Acumular (Fold) ==== | ==== Acumular (Fold) ==== |
| <code> | <code> |
| sumatoria :: [Int] -> Int | sumatoria :: [Int] -> Int |
| sumatoria [] = 0 | sumatoria [] = 0 |
| sumatoria (x:xs) = x + sumatoria xs | sumatoria (x:xs) = x + sumatoria xs |
| </code> | </code> |
| |
| Notar que en las funciones de tipo "fold" toman una lista como argumento. El resultado se obtiene de **acumular** los resultados de aplicar una función dada a cada uno de los elementos de la lista argumento. La forma en como se acumulan los resultados depende de cada función: en la función //sumatoria// se suman, en la función //productoria// se multiplican, etc. | Notar que en las funciones de tipo "fold" toman una lista como argumento. El resultado se obtiene de **acumular** los resultados de aplicar una función dada a cada uno de los elementos de la lista argumento. La forma en como se acumulan los resultados depende de cada función: en la función //sumatoria// se suman, en la función //productoria// se multiplican, etc. |
| | |
| | Probamos en algunos valores de entrada. |
| | |
| | Main> sumatoria [] |
| | 0 |
| | Main> sumatoria [0] |
| | 0 |
| | Main> sumatoria [0,0] |
| | 0 |
| | Main> sumatoria [1..3] |
| | 6 |
| | Main> sumatoria [1..10] |
| | 55 |
| | Main> sumatoria [1..10000] |
| | 50005000 |
| |
| ==== Seleccionar (Filter) ==== | ==== Seleccionar (Filter) ==== |
| |
| Notar que en las funciones de tipo "filter" toman una lista como argumento y devuelven una lista como resultado. La lista de resultado se obtiene de concatenar los elementos de la lista de argumento que devuelven un valor especificado para una función dada (típicamente, los elementos que devuelven True para un predicado). | Notar que en las funciones de tipo "filter" toman una lista como argumento y devuelven una lista como resultado. La lista de resultado se obtiene de concatenar los elementos de la lista de argumento que devuelven un valor especificado para una función dada (típicamente, los elementos que devuelven True para un predicado). |
| | |
| | Veamos como funciona. |
| | |
| | Main> empiezaM ["marta", "liliana", "esther", "mario"] |
| | ["marta","mario"] |
| | Main> empiezaM ["Merceditas", "Tabaré"] |
| | [] |
| | |
| | ==== Múltiples casos 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. |
| | |
| | <code> |
| | emparejar :: [String] -> [(String,String)] |
| | emparejar (x:y:xs) = (x,y) : emparejar xs |
| | emparejar [x] = [(x,x)] |
| | emparejar [] = [] |
| | </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]//. |
