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.

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 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.

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.

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 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:

1. tratar un número indeterminado de elementos (como en la inducción matemática)
2. 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:

1. 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),
2. 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
3. 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.

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

Otros ejemplo célebre de recursión con números es la 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.

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]

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.

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:

1. 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),
2. 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
3. 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.

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é"]
[]

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

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")]

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.

• 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.

• 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], [].

• 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.

• 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].

• 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.

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 ;)