En la clase anterior introdujimos el concepto de recursividad o recursión. En esta clase vamos a consolidarlo, repasando sus fundamentos y haciendo ejercicios para tratar de entenderlo.

En primer lugar, recordemos lo que se espera que pueda hacer un programa recursivo:

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

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.

La recursividad funciona para cualquier tipo de estructuras con un número indeterminado de elementos, como por ejemplo los números naturales.

Veamos por ejemplo la función repetir :: Int → a → [a], que dado un elemento lo repite n veces, dando como resultado una lista que contiene las repeticiones. En este caso la recursividad se dá en los naturales desde 0 hasta n. Este número n no lo conocemos a priori, por lo tanto a la hora de escribir el programa no podemos escribir qué hacer en cada uno de los casos desde 0 hasta n, sino que tenemos que usar un mecanismo general que diga qué hacer en un caso cualquiera de esta sucesión. La recursividad nos va a dar el mecanismo para pasar de un caso al siguiente todas las veces que sea necesario, y nosotros vamos a definir en el programa qué hacer al pasar de un caso cualquiera al siguiente. Veamos una posible solución para esta la función:

repetir :: Int -> a -> [a]
repetir 0 x = []                   -- caso base
repetir n x = x : repetir (n-1) x  -- caso recursivo

En esta función, lo que hacemos en cada caso es simplemente concatenar el elemento, que hemos llamado x, y volvemos a llamar a la misma función (llamada recursiva). Pero noten que al llamar la función de vuelta, decrementamos en 1 el argumento que hemos llamado n. De esta forma, garantizamos que en algún momento ese argumento va a ser 0, y ahí se va a aplicar el caso base, donde no se llama más a la función y por lo tanto el programa termina.

Veamos otro ejemplo, la función potencia :: Int → Int → Int, que toma dos enteros n y x, y calcula x^n usando multiplicación y recursividad. Esta función es muy parecida a la anterior: la recursividad se dá en los naturales, desde 0 hasta n, un n arbitrario que no conocemos a priori. Y lo que tendremos que hacer en un caso cualquiera de la función será multiplicar el número x por el resultado de multiplicar x todas las veces que nos haya indicado el argumento n, lo cual escribiremos como n-1, de la siguiente forma:

potencia :: Int -> Int -> Int
potencia 0 x = 1
potencia n x = x * potencia (n-1) x

Fíjense que en la función potencia, en el caso base devolvemos 1, mientras que en la función repetir devolvemos []. Esto es así porque el tipo del resultado para potencia tiene que ser un entero, y el tipo del resultado para repetir tiene que ser una lista. Si damos como resultado cualquier otra cosa, nos encontraremos con un error de tipos.

Pero además, no podemos devolver cualquier entero o cualquier lista: tienen que ser elementos que NO modifiquen el resultado final del cálculo. Para saber cuál ese elemento tenemos que fijarnos en la operación que estamos aplicando: multiplicación en un caso y concatenación en el otro. Para una operación cualquiera, existe un elemento que se llama neutro que tiene la propiedad de no modificar el resultado de esa operación, de tal modo que para una operación ☆, su neutro N y un elemento arbitrario p se da que:

p ☆ N = p

Ese elemento depende de cada operación, veamos algunos casos particulares:

p +  0     = p
p *  1     = p
p && True  = p
p || False = p

Esto será especialmente importante recordarlo para los acumuladores.

Las listas son una estructura que por definición contiene un número arbitrario de elementos, por lo tanto son el contexto natural para aplicar funciones recursivas. Hemos distinguido tres grandes tipos de funciones recursivas en listas:

• aplicaciones: toman una lista y devuelven otra lista que es el resultado de aplicar una función a todos los elementos de la lista original. Su signatura de tipos suele seguir el esquema

aplica :: [a] -> [b]

donde el tipo de la lista inicial no necesariamente tiene que ser el mismo que el de la lista resultante, ya que la función que aplicamos a cada elemento puede cambiar ese tipo (por ejemplo, si cambiamos de booleano a 0 o 1).

• filtros: toman una lista y devuelven solamente los elementos de esa lista que cumplen con un determinado predicado. Su signatura de tipos suele seguir el esquema

filtra :: [a] -> [a]

donde el tipo de la lista inicial tiene que ser exactamente el mismo que el de la lista resultante, ya que devolvemos elementos del mismo tipo solamente que podemos devolver menos elementos, descartando los que no cumplen el predicado (por ejemplo, los que no son pares).

• acumuladores: toman cada uno de los elementos de una lista y hacen alguna operación para acumular ese elemento con el resultado de hacer lo mismo con el resto de la lista. Su signatura de tipos suele seguir el esquema

acumula :: [a] -> b

fíjense que el tipo del resultado es distinto que el de la lista inicial, de hecho, ni siquiera es necesario que sea una lista. El tipo del resultado es exactamente el neutro de la operación que estemos aplicando para acumular el resultado (por ejemplo, en una sumatoria es el 0, en una productoria el 1, etc.).

Algunas funciones se corresponden exactamente con estos tipos generales. Otras funciones más complejas, en cambio, combinan varios de estos tipos de funciones para resolver un problema. Veamos ahora ejemplos de cada uno de estos tres tipos y luego ejemplos de combinaciones.

Las funciones de tipo aplicación toman una lista y devuelven otra lista que es el resultado de aplicar una función a todos los elementos de la lista original. Veamos algunos ejemplos:

duplicar :: [Int] -> [Int]
duplicar []     = []
duplicar (x:xs) = 2*x : duplicar xs

veintePorCiento :: [Float] -> [Float] 
veintePorCiento []     = []
veintePorCiento (x:xs) = 0.2*x : veintePorCiento xs

cuadrados :: [Int] -> [Int]
cuadrados []     = []
cuadrados (x:xs) = cuadrado x : cuadrados xs

cuadrado :: Int -> Int
cuadrado x = x^2

Entonces, la estructura general de una función de tipo aplicación es la siguiente:

___________ :: [a] -> [b]
___________ []     = []
___________ (x:xs) = _________ x : ___________ xs

Ahora que sabemos esto, resolvamos la función 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].

Una función tipo filtro toma una lista y devuelve los elementos de esa lista que cumplen con un determinado predicado.

Veamos funciones de tipo filtro que hemos creado:

soloTrue :: [Bool] -> [Bool]
soloTrue [] = []
soloTrue (x:xs) | x == True = x : soloTrue xs
                | otherwise =     soloTrue xs

soloPares :: [Int] -> [Int]
soloPares [] = []
soloPares (x:xs) | esPar x   =  x : soloPares xs
                 | otherwise =      soloPares xs

esPar :: Int -> Bool
esPar x = mod x 2 == 0

empiezaM :: [String] -> [String]
empiezaM [] = []
empiezaM (x:xs) | primeraEsM x = x : empiezaM xs
                | otherwise    =     empiezaM xs

primeraEsM :: [Char] -> Bool
primeraEsM xs = head xs == 'm'

¿Cuál es la estructura que tienen en común estas funciones?

__________ :: [a] -> [a]
__________ [] = []
__________ (x:xs) | ______ x  =  x : _____________ xs
                  | otherwise =      _____________ xs

Ahora que sabemos esto, resolvamos la función soloMultiplos3 :: [Int] → [Int] que dada una lista de enteros devuelve una lista que contiene sólo los múltiplos de 3 de la lista original. Ejemplo: soloMultiplos3 [6,5,12,21,22] = [6,12,21].

Los acumuladores son un tipo de funciones que toman cada uno de los elementos de una lista y hacen alguna operación para acumular ese elemento con el resultado de hacer lo mismo con el resto de la lista.

Más y más funciones fueron acumuladores, veamos algunas:

sumatoria :: [Int] -> Int
sumatoria []     = 0
sumatoria (x:xs) = x + sumatoria xs

productoria :: [Int] -> Int
productoria []     = 1
productoria (x:xs) = producto x (productoria xs)

producto :: Int -> Int -> Int
producto x y = x*y

concatenaInt :: [[Int]] -> [Int]
concatenaInt []       = []
concatenaInt (xs:xss) = (++) xs (concatenaInt xss)

¿Cuál es la estructura común de todas estas funciones? Para poder verla bien, debemos saber que todo operador que usemos entre sus dos argumentos, como +, : o ++, se puede usar también con la misma sintaxis que cualquier otra función, es decir, delante de sus dos argumentos. Para ello hay que poner al operador entre paréntesis, como hemos visto en el último de los ejemplos de arriba con el operador ++. De esta forma, el caso recursivo de la función sumatoria también se puede escribir así:

sumatoria (x:xs) = (+) x (sumatoria xs)

Donde el primer número a sumar es x y el segundo es sumatoria xs, es decir, el resultado de resolver la función sumatoria xs.

Entonces, la estructura común de todas estas funciones es:

_________ :: [a] -> b
_________ []     = _____
_________ (x:xs) = _____ x (_________ xs)

Como el resultado de la función no es una lista, el resultado del caso base no es una lista vacía. El resultado del caso base debe ser definido para cada función, ya que debe ser el neutro del operador que se utilice en la función.

Ahora que sabemos esto, resolvamos la función longitud :: [Int] → Int que dada una lista de enteros computa su largo. Ejemplo: longitud [3,0,-2] = 3.

Otro ejemplo: 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.

Más ejercicios: 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.

Y finalmente, 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.

Muchas funciones necesitan hacer cosas complejas, y para eso combinan dos o más de los tipos de funciones recursivas en listas que hemos visto. Veamos los siguientes ejemplos:

La función sumaPares :: [Int] → Int, que suma sólo los elementos pares de una lista. Esta función es una combinación de un filtro (nos quedamos solamente con los pares) y un acumulador (sumamos esos elementos con los que nos hemos quedado).

sumaPares :: [Int] -> Int
sumaPares [] = 0
sumaPares (x:xs) | mod x 2 == 0 = x + sumaPares xs
                 | otherwise    =     sumaPares xs

Fíjense que el resultado es el resultado propio de un acumulador, es decir, no es una lista, por lo tanto para el caso base tenemos que usar el neutro de la operación, en este caso, como la operación es la suma, el resultado para el caso base es el 0.

También podríamos definir la función de forma que queden más separados el filtro y el acumulador, definiendo las funciones por separado y usándolas luego combinadas, primero aplicando el filtro y luego sumando los elementos que quedaron seleccionados en el filtro. Para indicar que primero se tiene que aplicar una operación y después la otra, usamos paréntesis:

sumaPares' :: [Int] -> Int
sumaPares' xs = suma (pares xs)

pares :: [Int] -> [Int]
pares [] = []
pares (x:xs) | mod x 2 == 0 = x : pares xs
             | otherwise    =     pares xs

suma :: [Int] -> Int
suma [] = 0
suma (x:xs) = x + suma xs

Fíjense que ahora no tenemos que definir caso base y caso recursivo para definir sumaPares, porque ya están definidos en las funciones sumatoria y soloPares.

Pero no les resultan muy familiares estas funciones pares y suma? Efectivamente, son nuestras viejas amigas soloPares y sumatoria, así que podríamos directamente usar ésas para definir sumaPares, de la siguiente forma:

sumaPares'' :: [Int] -> Int
sumaPares'' xs = sumatoria (soloPares xs)

Corto, fácil de leer y reusando código! Qué más queremos!

Veamos otros ejemplos: 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. En este caso estamos combinando una aplicación (calcular el 5% y sumarlo) y un acumulador (sumar todos los elementos de la lista a la que se ha aplicado el acumulador). También en este caso podemos definir primero las funciones por separado: la aplicación (calcular y sumar 5%) y el acumulador (sumatoria), y aplicarlos combinadamente, primero la aplicación y después la sumatoria.

Cómo calculamos la función edadPromedio:: [(String,Int)] → Int, que dada una lista de pares (nombre,edad), retorna el promedio de edad de las personas? En este caso tenemos un acumulador (el promedio), y vamos a necesitar algo más…

La recursión en dos argumentos aplica los mismos principios de la recursión, pero a dos argumentos a la vez. Es decir, en un mismo paso de recursión, vamos a consumir dos estructuras de datos, por ejemplo, dos listas. En cualquiera de los pasos, puede suceder que sea vacía una de las estructuras, la otra, ambas o bien que ambas sean no vacías, por lo tanto, en general hay que tener en cuenta 4 casos.

Veamos como ejemplo la función abrochar:

abrochar :: [a] -> [b] -> [(a,b)]
abrochar [] []         = []
abrochar (x:xs) []     = []
abrochar [] (y:ys)     = []
abrochar (x:xs) (y:ys) = (x,y) : abrochar xs ys

Como 3 de los 4 casos de abrochar devuelven el mismo resultado, intentamos ponerlos en un mismo patrón, un patrón irrefutable que se aplica siempre que no se puede aplicar el patrón del caso recursivo:

abrochar' :: [a] -> [b] -> [(a,b)]
abrochar' (x:xs) (y:ys) = (x,y) : abrochar xs ys
abrochar' _ _ = []

La función nesimo, que devuelve el n-ésimo elemento de una lista (comenzando de 0), también se puede definir como recursiva en dos argumentos, donde uno es una lista y el otro un natural:

nesimo :: Int -> [a] -> a
nesimo _ []         = error "la lista está vacía"
nesimo 0 (x:xs)     = x
nesimo (n+1) (x:xs) = nesimo n xs

Vemos que para esta función sólo hay que definir 3 casos porque el caso nesimo 0 [] cae dentro del caso nesimo _ []. Vemos también que en el caso recursivo no se devuelve ningún resultado, sino que lo que se hace es recorrer la lista según va indicando el número, reduciendo el número en 1 cada vez que se recorre un elemento de la lista, hasta que se llega al punto indicado por el número, que se habrá convertido en 0, y ahí se devuelve el elemento correspondiente, que será, justamente, el n-ésimo. Notar que esta definición se corresponde con la definición de n-ésimo que vimos en el formalismo.

Veamos ahora una función un poco más compleja: encuentraEstafador. Esta función sirve para encontrar personas que estén cobrando subsidio por desempleo y a la vez trabajando, por ejemplo, en la municipalidad. Para encontrarlos, partimos de dos listas, una con las personas que reciben subsidio de desempleo y otra con los trabajadores de la municipalidad. Queremos es encontrar a todas las personas que estén en las dos listas. Podemos hacerlo de una forma muy poco eficiente:

encuentraEstafador :: [Int] -> [Int] -> [Int]
encuentraEstafador [] _      = []
encuentraEstafador (x:xs) ys | existe x ys = x : encuentraEstafador xs ys
                             | otherwise       =     encuentraEstafador xs ys

Esta versión es poco eficiente porque para cada elemento de la primera lista tenemos que recorrer toda la segunda lista. Sin embargo, si suponemos que las listas están ordenadas, podríamos aprovechar este hecho para recorrerlas a ambas de forma más eficiente.

• A partir de la siguiente base de conocimiento en prolog, crear las reglas necesarias para que el intérprete nos diga si una persona alérgica a la frutilla puede comer helado de frutilla:

esAlérgico(pepe,kiwi).
esAlérgico(juan,frutilla).
esAlérgico(maría,melocotón).

tiene(helado,Y) :- helado(Y).
tiene(torta,Y) :- torta(Y).

• Definir la función estanOrdenados, estanOrdenados :: (Int,Int) → Bool, que dado un par de números enteros devuelve True si los números están ordenados de menor a mayor.

• Definir la función cuadradoOcubo, cuadradoOcubo:: Int → Int, que dado un entero n, devuelve su cuadrado si n es par y su cubo si n es impar.

• Definir la función dobleONada, dobleONada Int → Int, que dado un entero n, devuelve el doble (es decir, n*2) si n es positivo y 0 si n es negativo.

• Definir la función multiplo, multiplo :: Int → Int → Bool, que dados dos enteros n y m determina si n es múltiplo de m.

• Definir la función restaPositiva, restaPositiva:: (Int,Int) → Int, que dado un par de enteros, devuelve el valor de la resta del mayor menos el menor.

• Definir la función esSigno, esSigno :: String → (String,String,String) → Bool, que dado un string s que representa un signo zodiacal, una tresupla (n,t,z) que representa el nombre, el trabajo y el signo zodiacal de una persona, devuelve True si la persona es del signo s y False si es de cualquier otro signo.

Ejemplo: esSigno ``aries (``Ana,recepcionista,aries) = True.

Ejemplo: esSigno ``leo'' (``Mario'',''tornero'',''libra'') = False.

• Definir la función cuatroCabezas, cuatroCabezas :: [ [ a ] ] → (a,a,a,a), que dada una lista de listas de cualquier tipo devuelve una cuatrupla con los primeros elementos de las cuatro primeras listas de la lista original.

Ayuda: se puede usar la función “head” definida en el preámbulo, o definir la función “cabeza”.

• Definir la función librosRecomendados, librosRecomendados :: [(String,Bool)] → [String], que dada una lista de pares (nombre,esRecomendado), devuelve una lista con sólo los nombres de los libros recomendados.

Ejemplo: librosRecomendados [(``El nombre de la Rosa,False),(``Los pilares de la Tierra,True),(``Luces del Norte,True)] = [``Los pilares de la Tierra,``Luces del Norte].

• Definir la función peliculasAccion, peliculasAccion :: [(String,Bool)] → [String], que dada una lista de pares (nombre,esAccion), devuelve una lista con solo los nombres de las películas de acción.

Ejemplo: peliculasAccion [(“Rambo”,True),(“E.T.”,False),(“Duro de Matar”,True)] = [“Rambo”,“Duro de Matar”].

• Definir la función cuadrados, cuadrados :: [Int] → [Int], que dada una lista de enteros xs devuelve una lista con el cuadrado de cada uno de los miembros de xs.

• Definir la función soloEntre0y9, soloEntre0y9 :: [Int] → [Int], que dada una lista de enteros devuelve una lista que contiene sólo aquellos miembros de la lista original mayores o iguales que 0 y menores o iguales que 9.

• Definir la función sumatoriaNegativa, sumatoriaNegativa :: [Int] → Int, que dada una lista de enteros, devuelve el resultado de restar cada uno de ellos.

Ejemplo: sumatoriaNegativa [1,2,3] = -6.

• Definir la función productoTriplas, productoTriplas :: [(Int,Int,Int)] → Int, que dada una lista de triplas de enteros, devuelve el resultado de multiplicar todos los miembros de todas las triplas.

• Definir la función suma2ysuma, suma2ysuma:: [Int] → Int, que dada una lista de enteros, suma 2 a cada uno de sus elementos y devuelve la suma de todos ellos.

Ejemplo: suma2ysuma [1,2,3] = 12.

• Definir la función sumatoriaEsPar, sumatoriaEsPar:: [Int] → Bool, que dada una lista de enteros, suma cada uno de sus elementos y devuelve True si el resultado es par y False si es impar.

Ejemplo: sumatoriaEsPar [1,2,3,4] = True.

• Definir la función cuantos0, cuantos0 :: [Int] → Int, que dada una lista de enteros devuelve un entero con la cantidad de n˙meros 0 que hay en la lista original.

Ayuda: recordar cómo se hizo la función “longitud”.

• Definir la función cuantosEntre, cuantosEntre :: Int → Int → [Int] → Int, que dados dos números n y m y una lista de enteros xs, devuelve la cantidad de números de xs que están entre n y m.

Ejemplo: cuantosEntre 30 40 [15,45,36,20,63,32] = 2

• Definir la función paresHasta, paresHasta :: Int → [Int], que dado un número devuelve la lista de pares que hay desde 0 hasta ese número.

• Definir la función multiplica, multiplica:: Int → Int → Int, que dado dos enteros x y y, calcula x * y usando sólo suma y recursividad.

• Definir la función impuestoLujo, 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, 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 iguales :: Eq a ⇒ [a] → [a] → Bool que decide si dos listas son iguales.

• Definir encuentraEstafador': [Int] → [Int] → [Int], que opera sobre dos listas ordenadas de menor a mayor, y aprovecha este hecho para recorrerlas una sola vez.

• Activar con :set +s para que imprima el número de pasos de reducción que realizó para cada evaluación y comprobar que encuentraEstafador es menos eficiente que encuentraEstafador'.

• Supongamos ahora que el listado de las personas que reciben subsidio por desempleo es una lista de tuplas (dni,nombre,mesesDeDesempleo), con los siguientes tipos: (Int,String,Int) y el listado de personas que trabajan en la municipalidad, se aporta la siguiente información de cada persona: (nombre,dni,fechaDeNacimiento), con los tipos: (String,Int,String). Utilizando map y funciones auxiliares obtener el estafador de los siguientes listados:

listadoSubsidio :: [(Int,String,Int)]
listadoSubsidio = [(23763956,"Pedrito Rico",7), (36518184,"Daniel Socolof",2), (37643221,"Amaranta Buendía",1)]
listadoMuni :: [(String,Int,String)]
listadoMuni = [("Rubén Daniele",7632663,"21/12/1957"),("Amanda Buendía",37643221,"04/06/1987"),("Caridad Canelón",41122332,"29/2/2000")]