Diferencias

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

--- introalg:taller09_5 [2009/04/26 02:50] – laura
+++ introalg:taller09_5 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
@@ Línea 1: / Línea 1: @@
 ====== 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 =====
@@ Línea 65: / Línea 67: @@
 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):
+<code>
+factorial (n+1) = (n+1) * factorial n
+</code>
+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:
+<code>
+duplicar (x:xs) = x*2 : duplicar xs
+</code>
+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:
+<code>
+sumatoria (x:xs) = x + sumatoria xs
+</code>
+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  =====
@@ Línea 104: / Línea 128: @@
 ==== Definición de factorial ====
-Veamos el ejemplo más conocido, la función //factorial//:
+Veamos un ejemplo muy conocido, la función //factorial//:
 <code>
@@ Línea 202: / Línea 226: @@
 </code>
+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.
@@ Línea 208: / Línea 232: @@
 ==== Aplicar (Map) ====
-Veamos ahora otro ejemplo, con la función //duplicar.xs//, //duplicar :: [Int] -> [Int]// que dada una lista multiplica por 2 cada uno de sus elementos (ej.: //duplicar [2,4,8] = [4,8,16]//).
+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:
@@ Línea 251: / Línea 277: @@
 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.xs// estaría bien definida de la siguiente forma:
+La función ''duplicar'' estaría bien definida de la siguiente forma:
 <code>
@@ Línea 273: / Línea 299: @@
 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".
+<code>
+empiezaM :: [String] -> [String]
+empiezaM [] = []
+empiezaM (x:xs) | cabeza x == 'm' = x : empiezaM xs
+                | otherwise       = empiezaM xs
+</code>
+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é"]
+  []
@@ Línea 278: / Línea 326: @@
 ==== Acumular (Fold) ====
-Veamos la función //sumatoria.xs//, //sumatoria : [Int] -> Int//, que dada una lista devuelve la suma de sus elementos.
+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.
 <code>
   sumatoria :: [Int] -> Int
@@ Línea 286: / Línea 335: @@
 </code>
-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.
+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.
@@ Línea 302: / Línea 351: @@
   Main> sumatoria [1..10000]
   50005000
-==== Seleccionar (Filter) ====
-Veamos la función //empiezaM.xs//, //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".
-<code>
-empiezaM :: [String] -> [String]
-empiezaM [] = []
-empiezaM (x:xs) | cabeza x == 'm' = x : empiezaM xs
-                | otherwise       = empiezaM xs
-</code>
-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 como funciona.
-  Main> empiezaM ["marta", "liliana", "esther", "mario"]
-  ["marta","mario"]
-  Main> empiezaM ["Merceditas", "Tabaré"]
-  []
 ==== 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.xs//, //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.
+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.
 <code>
@@ Línea 339: / Línea 368: @@
   [("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:
+<code>
+duplicar([],[]).
+duplicar([X|Xs],[Y|Ys]) :- Y is (X*2), duplicar(Xs,Ys).
+</code>
+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 =====
@@ Línea 344: / Línea 381: @@
 === Aplicar ===
-   * Definir la función //veintePorCiento.xs//, //veintePorCiento : [Float] -> [Float]// que dada una lista de números  devuelve una lista con el 20% de cada elemento de la lista.
+   * 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.n.xs//, //porCiento : Int -> [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]//. Puede ser útil la función ''fromIntegral'' que transforma un ''Int'' en ''Float''.
+   * 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.n.xs//, //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]//.
+   * 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.xs//, //productoria : [Int] -> Int// que dada una lista devuelve el producto de sus elementos.
+   * 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.xs//, //longitud : [Int] -> Int// que dada una lista de enteros computa su largo. Ejemplo: //longitud.[3,0,-2] = 3//.
+  * 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.
-=== Filtrar ===
+   * Definir la función ''todos0y1 : [Int] -> Bool'' que dada una lista devuelve //True// si ésta consiste sólo de 0s y 1s.
-   * Definir la función //soloPares.xs//, //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 [0], [], [1], [0,0,0,0], [0,1,0,1], [1,2,3], ['a','b','c']
-  probar con [2,4,6,8], [0,1,2,3], [0,1], [1] y [].
+  * 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 //ningunFalse.xs//, //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]//.
+  * 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.
-  probar con [False], [True], [True,False,True], [False,True,False], [].
+  * 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.n//, //fib : Int -> Int//, que se define así: //fib (n+2) = fib (n+1) + fib n//.
+   * 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.xs//, //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).
+   * 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 //todos0y1.xs//, //todos0y1 : [Int] -> Bool// que dada una lista devuelve //True// si ésta consiste sólo de 0s y 1s. 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 ''repetir :: Int -> a -> [a]'' que dado un elemento lo repite n veces, dando como resultado una lista que contiene las repeticiones.
-  probar con [0], [], [1], [0,0,0,0], [0,1,0,1], [1,2,3], ['a','b','c']
+  probar con 8 y "bobo", 0 y 33 y 4 y [].
-  * Definir la función //hay0.xs//, //hay0 : [Int] -> Bool// que dada una lista //xs// devuelve //True// si ésta contiene algún 0. Ejemplo //hay0.[1,2] = False//, //hay0.[1,4,0,5] = True//.
+   * 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]//.
-  probar con [], [0,0,0,0], [1,2,3,4], [0] y [1,5,7,0,9]
+=== Miscelánea un poco más complicada ===
-   * Definir la función //repetir.n.x//, //repetir : Int -> a -> [a]// que dado un elemento lo repite n veces, dando como resultado una lista que contiene las repeticiones.
+  * 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.
-  probar con 8 y "bobo", 0 y 33 y 4 y [].
+=== y como siempre... ===
+Traten de escribir en prolog las funciones que definieron en haskell.
-   * Definir la función //esMultiploLista.n.xs//, //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]//.
+... y siempre nos quedarán las funciones para recomendar amigos en //facebook// y para saber si hay una conexión entre dos ciudades ;)