====== Recursividad ====== En esta clase vamos a ver ejemplos principalmente en haskell, pero los principios que aprendamos se aplican igualmente a prolog, que tiene el mismo manejo de la recursividad y las listas, con una sintaxis muy parecida, que vemos en el último apartado de esta clase, antes de los ejercicios. ===== Para qué sirve la recursividad ===== Hasta este momento habíamos visto funciones que llamaban a otras funciones, como por ejemplo ''ordenaSiPositivos'', que llamaba a ''ambosPositivos'' para saber si los números con los que estaba tratando eran positivos o no, o la regla ''suegra'' en prolog, que usaba las reglas ''madre'' y ''pareja''. Ahora veremos funciones que se llaman a sí mismas, lo cual es un mecanismo muy fuerte y bien conocido llamado [[http://es.wikipedia.org/wiki/Recursi%C3%B3n|recursividad, recurrencia o recursión]]. Este mecanismo sirve para resolver problemas que requieren un número arbitrario de aplicaciones de la misma función. Por ejemplo, recordemos el ejemplo de la familia en prolog. Tenemos definido ''progenitor'', ''padre'' y ''abuelo'', pero cómo podríamos definir ''antepasado''? Sin pensar mucho, se nos ocurre la siguiente forma de expresarlo: antepasado(X,Y) :- progenitor(X,Y). antepasado(X,Y) :- progenitor(X,Z), progenitor(Z,Y). Eso nos lleva hasta los abuelos, pero y los bisabuelos? y los tatarabuelos? Podríamos hacer algo así: antepasado(X,Y) :- progenitor(X,Y). antepasado(X,Y) :- progenitor(X,Z), progenitor(Z,Y). antepasado(X,Y) :- progenitor(X,Z1), progenitor(Z1,Z2), progenitor(Z2,Y). antepasado(X,Y) :- progenitor(X,Z1), progenitor(Z1,Z2), progenitor(Z2,Z3), progenitor(Z3,Y). Y si queremos encontrar a nuestros antepasados de la Edad Media? Cuántas reglas tendremos que hacer? Por suerte, podemos usar recursividad: antepasado(X,Y) :- progenitor(X,Y). antepasado(X,Y) :- progenitor(X,Z), antepasado(Z,Y). De esta forma podemos llegar a cualquier antepasado, sin importar cuántas generaciones separen al descendiente Y del antepasado X. Veamos cómo funcionaría, por ejemplo si queremos saber si ''pepe'' es antepasado de ''lolo'' dada la siguiente base de conocimiento y la regla para antepasados que recién vimos: progenitor(pepe,esteban). progenitor(esteban,julián). progenitor(julián,raimundo). progenitor(raimundo,lolo). Veamos la traza de la pregunta ''antepasado(pepe,lolo).'': [trace] ?- antepasado(pepe,lolo). Call: (8) antepasado(pepe, lolo) ? creep Call: (9) progenitor(pepe, lolo) ? creep <== trata de aplicar la primera regla de "antepasado"... Fail: (9) progenitor(pepe, lolo) ? creep <== ... y falla Redo: (8) antepasado(pepe, lolo) ? creep <== aplica la segunda regla de "antepasado" Call: (9) progenitor(pepe, _L176) ? creep <== busca satisfacer la primera parte del cuerpo de la regla, progenitor(X,Z) Exit: (9) progenitor(pepe, esteban) ? creep <== puede satisfacer la primera parte del cuerpo de la regla, con X=pepe y Z=esteban Call: (9) antepasado(esteban, lolo) ? creep <== busca satisfacer la segunda parte del cuerpo de la regla, antepasado(Z,Y), para ello aplicará reglas de "antepasado" con los valores de variable X=esteban y Y=lolo Call: (10) progenitor(esteban, lolo) ? creep <== trata de aplicar la primera regla de "antepasado"... Fail: (10) progenitor(esteban, lolo) ? creep <== ... y falla Redo: (9) antepasado(esteban, lolo) ? creep <== aplica la segunda regla de antepasado Call: (10) progenitor(esteban, _L187) ? creep <== busca satisfacer la primera parte del cuerpo de la regla, progenitor(X,Z), donde ahora X=esteban Exit: (10) progenitor(esteban, 'julián') ? creep <== puede satisfacer la primera parte del cuerpo de la regla, con X=esteban y Z=julián Call: (10) antepasado('julián', lolo) ? creep <== busca satisfacer la segunda parte del cuerpo de la regla, antepasado(Z,Y), para ello aplicará reglas de "antepasado" con los valores de variable X=julián y Y=lolo Call: (11) progenitor('julián', lolo) ? creep <== trata de aplicar la primera regla de "antepasado"... Fail: (11) progenitor('julián', lolo) ? creep <== ... y falla Redo: (10) antepasado('julián', lolo) ? creep <== aplica la segunda regla de antepasado Call: (11) progenitor('julián', _L198) ? creep <== busca satisfacer la primera parte del cuerpo de la regla, progenitor(X,Z), donde ahora X=julián Exit: (11) progenitor('julián', raimundo) ? creep <== puede satisfacer la primera parte del cuerpo de la regla, con X=julián y Z=raimundo Call: (11) antepasado(raimundo, lolo) ? creep <== busca satisfacer la segunda parte del cuerpo de la regla, antepasado(Z,Y), para ello aplicará reglas de "antepasado" con los valores de variable X=raimundo y Y=lolo Call: (12) progenitor(raimundo, lolo) ? creep <== trata de aplicar la primera regla de "antepasado"... Exit: (12) progenitor(raimundo, lolo) ? creep <== ... y tiene éxito!!! se cumple el cuerpo de la regla, por lo tanto Exit: (11) antepasado(raimundo, lolo) ? creep <== podemos satisfacer la cabeza: que raimundo es antepasado de lolo, con lo cual se satisfizo el cuerpo de la regla anterior Exit: (10) antepasado('julián', lolo) ? creep <== y podemos satisfacer la cabeza: que julián es antepasado de lolo, con lo cual se satisfizo el cuerpo de la regla anterior Exit: (9) antepasado(esteban, lolo) ? creep <== y podemos satisfacer la cabeza: que esteban es antepasado de lolo, con lo cual se satisfizo el cuerpo de la regla anterior Exit: (8) antepasado(pepe, lolo) ? creep <== y podemos satisfacer la cabeza: que pepe es antepasado de lolo, con lo cual se satisfizo nuestra pregunta inicial! true ; Fíjense que hemos repetido el mismo proceso varias veces, y podríamos haberlo aplicado tantas como fuera necesario hasta encontrar lo que buscábamos. Este tipo de solución sirve para tratar todos los problemas en los que tenemos que hacer la misma cosa un número **indeterminado** de veces. Esto se consigue definiendo a una función de manera tal que la función se contiene a sí misma en su propia definición. ===== Recursividad e inducción ===== La recursividad se implementa de forma muy parecida a la inducción matemática, que ustedes ya han visto en Álgebra. Para escribir funciones recursivas, si tenemos una función ''f'' que suponemos que anda para ''n'', usamos esa función para definir ''n+1''. Definimos el caso ''n+1'' como la operación que une la parte de ''n+1'' y la parte de ''n''. La parte de ''n'' se calcula aplicando la función ''f'' a ''n'', y el cálculo de ''n+1'' se define en este mismo lugar. Veamos algunos ejemplos. Tomemos la parte de la definición de ''factorial'' que dice qué hacer con el caso ''n+1'' (la definición completa se encuentra más abajo): factorial (n+1) = (n+1) * factorial n Vemos que hemos definido cómo cómo unir ''n+1'' con el resultado de aplicar ''factorial'' a ''n'': multiplicando ''n+1'' con ''factorial n''. Por lo que respecta a ''n+1'', en este caso no definimos ninguna operación extra sobre él. Veamos otro ejemplo, ahora con listas. En listas, el caso ''n+1'' se transforma en el caso ''(x:xs)'', asumimos es que tenemos una función que anda para el caso de la lista ''xs'' y definimos qué hacer con el caso en que añadimos un elemento más a esa lista. Veamos por ejemplo la parte inductiva de la función ''duplicar'', que toma una lista de enteros y devuelve la misma con todos sus elementos duplicados: duplicar (x:xs) = x*2 : duplicar xs Vemos que hemos definido cómo unir el caso ''n+1'' (la cabeza de la lista) con el resultado de duplicar la lista hasta ''x'' (''duplicar xs''): concatenándolo mediante el operador '':''. Además, definimos que a la cabeza de la lista hay que aplicarle la operación ''*2''. Otro ejemplo más con listas, el caso inductivo de la sumatoria: sumatoria (x:xs) = x + sumatoria xs La cabeza de la lista se une mediante la operación de suma con el resultado de aplicar ''sumatoria'' al resto de la lista, y no se le hace ninguna operación específica a la cabeza de la lista. ===== Caso base y caso inductivo ===== La recursividad permite que una función se llame a sí misma un número indeterminado de veces. En informática añadimos un requisito más a las funciones recursivas: exigimos a una función recursiva que **termine**. Puede suceder que una función recursiva mal definida no termine nunca, sino que caiga en lo que llamamos un **[[http://en.wikipedia.org/wiki/Infinite_loop|bucle infinito]]**. Por ejemplo, la siguiente función: sucesion :: Int -> [Int] sucesion n | n > 0 = n : sucesion (n+1) | n <= 0 = sucesion 1 En esta función, si ''n'' es positivo, se va a aplicar la función ''sucesion'', con el efecto de concatenar ''n'' y aplicar la función ''sucesion'' con ''(n+1)'' como argumento. Evidentemente, ''(n+1)'' también será positivo, así que la función se aplicará infinitamente. Si ''n'' es negativo o 0, se aplicará ''sucesion 1'', con lo cual se llamará a ''sucesion'' con el número 1 como argumento. Como 1 es positivo, entraremos en el mismo bucle que veíamos en el caso anterior. Para evitar caer en un bucle infinito, las funciones recursivas tienen dos partes: el/los caso/s base y el caso recursivo. El **caso base** es el que evita que nos metamos en un bucle infinito, es el caso que hace parar la recursión ya que __no llama a la función__. El **caso recursivo** es aquél en el que una función se llama a sí misma, y es el que hace que la recursión continúe hasta que se encuentre con el caso base. Tanto el caso recursivo como el caso base tienen condiciones de aplicación, que son justamente los **//casos//** (que normalmente obtenemos después de un análisis por casos del problema a solucionar). Para evitar meternos en un bucle infinito, es importante que el caso recursivo modifique su condición de aplicación, si no, mientras la condición del caso recursivo sea válida, seguirá aplicándose... infinitamente! Veamos un ejemplo parecido al anterior donde sí se modifica la condición de aplicación de forma que se llegue a algún punto en el que no se pueda aplicar más. sucesionInversa :: Int -> [Int] sucesionInversa n | 0<=n = n : sucesionInversa (n-1) | n<0 = [] En esta función, si //n// es negativo, se corta la recursividad, y además, para cualquier valor de //n//, sabemos que en algún momento vamos a llegar a un valor negativo, ya que en cada aplicación del paso recursivo se decrementa el valor de n. Entonces, los programas recursivos tienen que cumplir dos requisitos: - tratar un número indeterminado de elementos (como en la inducción matemática) - terminar en algún momento (a diferencia de la inducción matemática) Para garantizar que se cumplen estos dos requisitos, los programas o funciones recursivos tienen que tener las siguientes tres propiedades: - la función se llama a sí misma por lo menos en uno de los casos de su definición (caso(s) recursivo o inductivo), - la función NO se llama a sí misma por lo menos en uno de los casos de su definición (caso(s) base), y - la condición de aplicación del caso recursivo se modifica cada vez que se aplica éste, de forma que eventualmente no se cumple más la condición y se llega al caso base. El primer requisito garantiza que la función puede tratar un número indeterminado de elementos, mientras que los dos siguientes requisitos garantizan que la función va a terminar en algún momento. ==== Definición de factorial ==== Veamos un ejemplo muy conocido, la función //factorial//: factorial :: Int -> Int factorial 0 = 1 -- caso base factorial (n+1) = (n+1) * factorial n -- caso inductivo En esta función, el caso base se da cuando //n==0//; en ese caso no se llama a la función misma si no que se realiza una acción y se termina. En cambio, mientras //n>0// se aplica la función y se vuelve a llamar a sí misma. Notemos que la condición de aplicación del caso recursivo se va modificando, es decir, //n// se va modificando de forma que en algún momento llegará a ser 0 y ahí se aplicará el caso base. Eso nos garantiza que el programa terminará y no nos meteremos en un bucle infinito. Veamos cómo funciona //factorial// para el número 3: factorial 3 = {factorial n = n * factorial (n-1)} 3 * factorial (3-1) = {álgebra} 3 * factorial (2) = {factorial n = n * factorial (n-1)} 3 * 2 * factorial (2-1) = {álgebra} 3 * 2 * factorial (1) = {factorial n = n * factorial (n-1)} 3 * 2 * 1 * factorial (1-1) = {álgebra} 3 * 2 * 1 * factorial (0) = {factorial 0 = 1} 3 * 2 * 1 * 1 = {álgebra} 6 ==== Definición de Sucesión de Fibonacci ==== Otros ejemplo célebre de recursión con números es la [[http://es.wikipedia.org/wiki/Sucesi%C3%B3n_de_Fibonacci|Sucesión de Fibonacci]]. fib (n+2) = fib (n+1) + fib n Una particularidad de la Sucesión de Fibonacci es que es **doblemente recursiva**, ya que se llama dos veces a sí misma en cada paso, y no tiene un caso base, sino dos: fib 0 = 0 y fib 1 = 1. ==== Otro ejemplo ==== Recuerdan la función ''pip'' de la clase anterior? podemos generalizar las funciones //unidad, decena, etc.// en una que nos dé el dígito n-ésimo de la representación decimal, pero para eso necesitamos usar **funciones recursivas**. digitos :: Int -> [Int] digitos 0 = [] digitos n = n `mod` 10 : (digitos (n `div` 10)) La probamos para ver como opera Main> digitos 0 [] Main> digitos 1 [1] Main> digitos 10 [0,1] Main> digitos 120 [0,2,1] Main> digitos 123123123 [3,2,1,3,2,1,3,2,1] ===== Recursividad en listas ===== La recursivdad, junto con el //pattern matching// que vimos en la clase anterior, nos ofrece una forma muy natural de recorrer listas. El caso base suele ser la lista vacía ''[]'', y el caso inductivo suele ser la lista con uno o más elementos ''(x:xs)''. El caso inductivo modifica su condición de aplicación eliminando elementos de la lista, de forma que en algún momento la lista queda vacía, con lo que se llega al caso base y el programa termina. Para separar la parte de la lista que ya se ha procesado de la parte que queda por procesar, se usa pattern matching: se distingue la cabeza de la lista, a la que habitualmente se aplica alguna operación, y la cola, a la que se aplica la función de vuelta. Notemos que la cola es la misma lista original pero con un elemento menos, justamente, la cabeza. Veamos un ejemplo, la función //negarTodos//, que, dada una lista de booleanos, nos devuelve la misma lista con todos sus elementos al revés, es decir, los ''true'' como ''false'' y los ''false'' como ''true'': negarTodos :: [Bool] -> [Bool] negarTodos [] = [] -- caso base negarTodos (x:xs) = not x : negarTodos xs -- caso inductivo Veamos cómo se aplica la función //negarTodos// a la lista [True,False,False,False,True]: negarTodos [True,False,False,False,True] = {negarTodos (x:xs)} not True : negarTodos [False,False,False,True] = {negarTodos (x:xs)} not True : not False : negarTodos [False,False,True] = {negarTodos (x:xs)} not True : not False : not False : negarTodos [False,True] = {negarTodos (x:xs)} not True : not False : not False : not False : negarTodos [True] = {negarTodos (x:xs)} not True : not False : not False : not False : not True : negarTodos [] = {negarTodos []} not True : not False : not False : not False : not True : [] = {lógica} False : True : True : True : True : [] = {definición de []} [False,True,True,True,False] Vamos a ver tres grandes tipos de funciones recursivas en listas: las aplicaciones (map), los filtros (filter) y los acumuladores (fold). Las aplicaciones toman una lista y devuelven la misma lista, después de aplicar una función a todos sus miembros. Ejemplos de aplicaciones son ''duplicar'', ''negarTodos'', ''convertirABinario'', etc. Los filtros toman una lista y devuelven solamente los elementos de la lista que cumplen una cierta condición. Ejemplos de filtros son ''soloPositivos'', ''peliculasBuenas'', ''empiezaPorA''. Los acumuladores toman una lista y devuelven el resultado de ir aplicando una operación sobre todos los elementos de esa lista y acumulando el resultado de aplicar esa operación. Ejemplos de filtros son ''sumatoria'', ''existe'', ''paraTodo''. Veamos cada uno de estos tipos de funciones en más detalle. ==== Aplicar (Map) ==== Las aplicaciones toman una lista y devuelven la misma lista, después de aplicar una función a todos sus miembros. Por lo tanto, su signatura de tipos suele ser de la forma ''func :: [a] -> [b]''. Por ejemplo, la función ''duplicar :: [Int] -> [Int]'', dada una lista multiplica por 2 cada uno de sus elementos (ej.: //duplicar [2,4,8] = [4,8,16]//). Recordemos los requisitos básicos de las funciones recursivas: - la función se llama a sí misma por lo menos en uno de los casos de su definición (caso(s) recursivo o inductivo), - la función NO se llama a sí misma por lo menos en uno de los casos de su definición (caso(s) base), y - la condición de aplicación del caso recursivo se modifica cada vez que se aplica éste, de forma que eventualmente no se cumple más la condición y se llega al caso base. Veamos varias formas en que la función estaría **MAL** definida, porque se incumplen alguno de los requisitos anteriores: duplicar :: [Int] -> [Int] duplicar [] = [] duplicar (x:xs) = 2*x : xs Probamos la función y obtenemos Main> duplicar [] [] Main> duplicar [10] [20] Main> duplicar [10,20] [20,20] Main> duplicar [10,20,30] [20,20,30] En este caso, la función **no se llama a sí misma**, así que sólo se aplicaría a la cabeza de la lista, y no a todo el resto. Por lo tanto, incumple el requisito número 1. Corregimos este error. duplicar :: [Int] -> [Int] duplicar [] = [] duplicar (x:xs) = 2*x : duplicar (x:xs) Probamos de nuevo la definición y obtenemos Main> duplicar [] [] Main> duplicar [10] [20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20 ... En este caso, el caso recursivo no modifica su condición de aplicación, así que nunca va a llegar al caso base y por lo tanto caerá en un bucle infinito. En este caso se está incumpliendo el requisito número 3, que requiere que la condición de aplicación del caso recursivo se modifique cada vez que se aplica éste, de forma que eventualmente no se cumple más la condición y se llega al caso base. En este caso, la lista no se modifica, no se achica, no se consume su cabeza en cada ocasión, y por eso nunca se llega a una lista vacía, que es la condición de aplicación del caso base. La función ''duplicar'' estaría bien definida de la siguiente forma: duplicar :: [Int] -> [Int] duplicar [] = [] -- caso base duplicar (x:xs) = 2*x : duplicar xs -- caso inductivo 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. ==== Seleccionar (Filter) ==== Los filtros toman una lista y devuelven solamente los elementos de la lista que cumplen una cierta condición. Veamos la función ''empiezaM :: [String] -> [String]'', que dada una lista de nombres (representados como //String// o //[Char]//, que son tipos equivalentes) nos devuelve todos aquellos nombres que empiezan con la letra "m". empiezaM :: [String] -> [String] empiezaM [] = [] empiezaM (x:xs) | cabeza x == 'm' = x : empiezaM xs | otherwise = empiezaM xs 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 cómo funciona. Main> empiezaM ["marta", "liliana", "esther", "mario"] ["marta","mario"] Main> empiezaM ["Merceditas", "Tabaré"] [] ==== Acumular (Fold) ==== Los acumuladores toman una lista y devuelven el resultado de ir aplicando una operación sobre todos los elementos de esa lista y acumulando el resultado de aplicar esa operación. Podemos verlo como que tenemos una pila de hojas (nuestra lista de partida) y una bola de papel arrugado como resultado. La función agarra cada hoja de papel y la une a la bola de papel arrugado, de forma que cuando terminamos con la pila de hojas tenemos una sola bola de papel que es el resultado de haber acumulado todas las hojas de la pila. Veamos la función ''sumatoria :: [Int] -> Int'', que dada una lista devuelve la suma de sus elementos. sumatoria :: [Int] -> Int sumatoria [] = 0 sumatoria (x:xs) = x + sumatoria xs 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 ==== 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 :: [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. emparejar :: [String] -> [(String,String)] emparejar (x:y:xs) = (x,y) : emparejar xs emparejar [x] = [(x,x)] emparejar [] = [] Veamos cómo funciona. Main> emparejar ["Pepa","Lola","Juan","Pili","Pedro"] [("Pepa","Lola"),("Juan","Pili"),("Pedro","Pedro")] ===== Sintaxis de listas en prolog ===== En prolog las listas tienen una sintaxis muy parecida a la de haskell: se escriben entre corchetes, separando a sus elementos por comas, por ejemplo: ''[mia, vincent, jules, yolanda]''. Para describir el patrón que distingue la cabeza de la lista de la cola, no se usa el operador '':'' como en haskell, sino el operador ''|''. Así, la función ''duplicar'' se definiría de la siguiente forma en prolog: duplicar([],[]). duplicar([X|Xs],[Y|Ys]) :- Y is (X*2), duplicar(Xs,Ys). Recordemos que en prolog tenemos que tratar el resultado de la función explícitamente como un argumento más de la función, cosa que en haskell únicamente tenemos que hacer en la signatura de tipos. ===== Ejercicios ===== === Aplicar === * Definir la función ''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]. * Generalizar la función ''veintePorCiento'' definiendo ''porCiento :: Float -> [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]//. * Generalizar la función ''duplicar'' definiendo ''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]//. probar con 1 [3,2,1], 10 [3,2,1], 0 [0,1,2] y [] 3. === Filtrar === * Definir la función ''soloPares :: [Int] -> [Int]'' que dada una lista de enteros devuelve una lista que contiene sólo los pares de la lista original. Ejemplo: //soloPares [6,5,12,21] = [6,12]//. probar con [2,4,6,8], [0,1,2,3], [0,1], [1] y []. * Definir la función ''ningunFalse :: [Bool] -> [Bool]'' que dada una lista de booleanos devuelve una lista sin ningún booleano False. Ejemplo //ningunFalse [False,True,False,True] = [True,True]//. probar con [False], [True], [True,False,True], [False,True,False], []. === Acumular === * Definir la función ''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 ''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 ''sonTodos0 :: [Int] -> Bool'', que dada una lista devuelve True si todos los elementos de la lista son 0. 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. * Definir la función ''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 ''hayun0 :: [Int] -> Bool'', que dada una lista devuelve True si hay algún 0 en la lista. * Definir la función ''existe :: a -> [a] -> Bool'', que dado un elemento y una lista, devuelve True si el elemento está en la lista. Fíjense que se trata de una generalización del ejercicio anterior. * Definir la función ''paratodo :: a -> [a] -> Bool'', que dado un elemento y una lista, devuelve True si todos los elementos de la lista son iguales al elemento que damos como primer argumento. === Miscelánea === * Escribir la función que calcula la Sucesión de Fibonacci, ''fib :: Int -> Int'', que se define así: //fib (n+2) = fib (n+1) + fib n//. probar con 4, 3, 2, 1 y 0. * Definir la función ''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 ''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 :: 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]//. === Miscelánea un poco más complicada === * Definir la función ''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 :: [(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 :: 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 :: [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 :: [(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 :: [(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:: [(String,Int)] -> Int'', que dada una lista de pares //(nombre,edad)//, retorna el promedio de edad de las personas. === y como siempre... === Traten de escribir en prolog las funciones que definieron en haskell. ... y siempre nos quedarán las funciones para recomendar amigos en //facebook// y para saber si hay una conexión entre dos ciudades ;)