====== Repaso de recursión ======
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:
- 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.
===== Recursión sin listas =====
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 [[http://www.cs.famaf.unc.edu.ar/wiki/doku.php?id=introalg:taller09_6#acumuladores_foldr|acumuladores]].
===== Recursión en listas =====
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.
==== Aplicaciones (map) ====
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]''.
==== Filtros (filter) ====
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]//.
==== Acumuladores (foldr) ====
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.
===== Combinando diferentes tipos =====
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...
===== Recursión en dos argumentos =====
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.
====== Ejercicios ======
==== Repaso de prolog ====
* 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).
==== Repaso de haskell ====
* 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".
==== Funciones recursivas ====
* 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.
===Ejercicios de recursión en dos argumentos===
* 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")]