Diferencias

Muestra las diferencias entre dos versiones de la página.

--- introalg:taller09_6 [2009/05/04 02:34] – laura
+++ introalg:taller09_6 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
@@ Línea 3: / Línea 3: @@
 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 que de un programa recursivo se espera:
+En primer lugar, recordemos lo que se espera que pueda hacer un programa recursivo:
-  - puede tratar un número indeterminado de elementos (como en la inducción matemática)
+  * tratar un número indeterminado de elementos (como en la inducción matemática)
-  - termina en algún momento (a diferencia de 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:
@@ Línea 19: / Línea 19: @@
 <code>
 repetir :: Int -> a -> [a]
-repetir 0 x = []
+repetir 0 x = []                   -- caso base
-repetir n x = x : repetir (n-1) x
+repetir n x = x : repetir (n-1) x  -- caso recursivo
 </code>
-La función ''potencia :: Int -> Int -> Int'', toma dos enteros //x// y //n//, y calcula //x^n// usando multiplicación y recursividad.
+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:
+<code>
+potencia :: Int -> Int -> Int
+potencia 0 x = 1
+potencia n x = x * potencia (n-1) x
+</code>
+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) ====
@@ Línea 43: / Línea 83: @@
 <code>
-cuadrado :: Int -> Int
-cuadrado x = x^2
 cuadrados :: [Int] -> [Int]
 cuadrados []     = []
 cuadrados (x:xs) = cuadrado x : cuadrados xs
-</code>
-<code>
+cuadrado :: Int -> Int
-rangoEdades :: [Int] -> [String]
+cuadrado x = x^2
-rangoEdades []     = []
-rangoEdades (x:xs) = rangoEdad x : rangoEdades xs
 </code>
@@ Línea 64: / Línea 98: @@
-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]//.
+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]''.
@@ Línea 74: / Línea 108: @@
 <code>
-esPar :: Int -> Bool
+soloTrue :: [Bool] -> [Bool]
-esPar = esDivisor 2
+soloTrue [] = []
+soloTrue (x:xs) | x == True = x : soloTrue xs
+                | otherwise =     soloTrue xs
+</code>
+<code>
 soloPares :: [Int] -> [Int]
 soloPares [] = []
 soloPares (x:xs) | esPar x   =  x : soloPares xs
                  | otherwise =      soloPares xs
+esPar :: Int -> Bool
+esPar x = mod x 2 == 0
 </code>
 <code>
-primeraEsM :: [Char] -> Bool
-primeraEsM xs = cabeza xs == 'm'
 empiezaM :: [String] -> [String]
 empiezaM [] = []
 empiezaM (x:xs) | primeraEsM x = x : empiezaM xs
                 | otherwise    =     empiezaM xs
+primeraEsM :: [Char] -> Bool
+primeraEsM xs = head xs == 'm'
 </code>
@@ Línea 100: / Línea 141: @@
                     | otherwise =      _____________ xs
-Ahora que sabemos esto, resolvamos 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]//.
+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) ====
@@ Línea 115: / Línea 156: @@
 <code>
-producto :: Int -> Int -> Int
-producto x y = x*y
 productoria :: [Int] -> Int
 productoria []     = 1
 productoria (x:xs) = producto x (productoria xs)
+producto :: Int -> Int -> Int
+producto x y = x*y
 </code>
@@ Línea 142: / Línea 183: @@
-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. Por lo tanto, en los acumuladores tendremos un argumento más que en las aplicaciones y los filtros, justamente, el neutro.
+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//.
+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//.
+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.
@@ Línea 157: / Línea 198: @@
 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.
+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).
-  * 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.
+<code>
-  * La función ''edadPromedio:: [(String,Int)] -> Int'', que dada una lista de pares //(nombre,edad)//, retorna el promedio de edad de las personas.
+sumaPares :: [Int] -> Int
+sumaPares [] = 0
+sumaPares (x:xs) | mod x 2 == 0 = x + sumaPares xs
+                 | otherwise    =     sumaPares xs
+</code>
+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:
+<code>
+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
+</code>
+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:
+<code>
+sumaPares'' :: [Int] -> Int
+sumaPares'' xs = sumatoria (soloPares xs)
+</code>
+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 =====
@@ Línea 198: / Línea 271: @@
 ====== 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:
+<code>
+esAlérgico(pepe,kiwi).
+esAlérgico(juan,frutilla).
+esAlérgico(maría,melocotón).
+tiene(helado,Y) :- helado(Y).
+tiene(torta,Y) :- torta(Y).
+</code>
+==== 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.
@@ Línea 208: / Línea 295: @@
   * 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.
@@ Línea 213: / Línea 309: @@
   * 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''].
+  Ejemplo: peliculasAccion [("Rambo",True),("E.T.",False),("Duro de Matar",True)] = ["Rambo","Duro de Matar"].
-  * 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 **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//.
@@ Línea 236: / Línea 328: @@
   * 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 **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 **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//.
@@ Línea 250: / Línea 339: @@
   * 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 la función //edadPromedio//, //edadPromedio:: [(String,Int)] -> Int//, que dada una lista de pares //(nombre,edad)//, retorna el promedio de edad de las personas.
@@ Línea 257: / Línea 344: @@
   * 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:
 <code>