Diferencias

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

--- introalg:taller09_8 [2009/05/15 01:03] – creado laura
+++ introalg:taller09_8 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
@@ Línea 11: / Línea 11: @@
 </code>
-Este tipo de generalización es posible en haskell porque haskell tiene una propiedad llamada **alto orden** que permite que una función sea tomada como argumento de otra función.
+Este tipo de generalización es posible en haskell porque haskell tiene una propiedad llamada **alto orden** que permite que una función sea tomada como argumento de otra función. Pero el alto orden nos permite no solamente tomar una función como argumento, sino también devolver una función como resultado. Esto resulta especialmente útil, porque nos permite usar funciones generales para definir funciones más concretas, concretando alguno de sus argumentos, como recién vimos en el caso de ''multiplicar''.
-Vamos a ver ahora cómo generalizamos los tres diferentes tipos de funciones recursivas en listas. De hecho, el preludio estándar de haskell ya tenemos definidas las funciones generales ''map'', ''filter'' y ''foldr'' que generalizan aplicaciones, filtros y acumuladores, respectivamente, pero en esta clase vamos a ver cómo se llega a esta generalización para adentrarnos en los procedimientos de generalización.
+Vamos a ver ahora cómo generalizamos los tres diferentes tipos de funciones recursivas en listas. De hecho, el preludio estándar de haskell ya tenemos definidas las funciones generales ''map'', ''filter'' y ''foldr'' que generalizan aplicaciones, filtros y acumuladores, respectivamente, pero en esta clase vamos a ver cómo se llega a esta generalización para adentrarnos en los procedimientos de generalización. Después vamos a ver ejemplos de funciones que devuelven funciones como resultado.
 Algo importante a tener en cuenta es que cuando definimos las versiones generalizadas de aplicaciones, filtros y acumuladores, definimos en esas versiones generalizadas el caso base y caso recursivo. Cuando definimos nuevas funciones usando estas generalizaciones, **no tenemos que volver a definir caso base y caso recursivo**, ya que las nuevas funciones usan la definición de caso base y caso recursivo de las funciones generalizadas. Véamoslo en concreto con los ejemplos.
-==== Aplicaciones (map) ====
+==== Tomar una función como argumento ====
+=== Aplicaciones (map) ===
 ¿No estamos ya cansados de escribir siempre lo mismo?
@@ Línea 57: / Línea 59: @@
 Ahora podemos reescribir todas las aplicaciones usando ''aplica'', y definiendo como argumento la función que queremos aplicar a todos los elementos de la lista. Por ejemplo:
 <code>
-duplicar' :: [Int] -> [Int]
+duplicar :: [Int] -> [Int]
 duplicar xs = aplica (*2) xs
-veintePorCiento' :: [Float] -> [Float]
+veintePorCiento :: [Float] -> [Float]
-veintePorCiento xs = veintePorCiento (porCiento 20) xs
+veintePorCiento xs = aplica (porCiento 20) xs
 </code>
 De esta forma, las funciones quedan mucho más compactas, más legibles y mucho más fáciles de mantener, ya que al tener que escribir menos, tenemos menos posibilidades de equivocarnos. Fíjense que ni siquiera tenemos que definir caso base y caso recursivo para cada una de las nuevas funciones que definimos con la función ''aplica'', porque ya tenemos definido caso base y caso recursivo en la función ''aplica'', y las funciones que definamos usando ''aplica'' usan esa definición de caso base y caso recursivo.
-==== Filtros (filter) ====
+=== Filtros (filter) ===
 Veamos funciones de //tipo filtro// que hemos creado:
@@ Línea 113: / Línea 115: @@
 Observemos que en el caso de los filtros, los elementos de la lista resultado tienen que ser del mismo tipo que los elementos de la lista que damos como argumento (''[a] -> [a]''), ya que la función filtro **no modifica** los elementos, sino que solamente determina si deben o no deben formar parte del resultado. En cambio, en las aplicaciones el resultado puede ser de distinto tipo que el argumento (''[a] -> [b]''), porque la aplicación sí puede modificar los elementos de la lista de entrada, incluso cambiándolos de tipo. Notemos que ''[a] -> [b]'' significa que **podemos** encontrar tipos distintos (como en ''rangoEdad'') pero esto no es obligatorio: podemos encontrar que ''a'' y ''b'' representen el mismo tipo (como en ''duplicar'').
-==== Acumuladores (foldr) ====
+=== Acumuladores (foldr) ===
 Más y más funciones fueron acumuladores, veamos algunas:
@@ Línea 132: / Línea 134: @@
 </code>
-¿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í:
+¿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. 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//.
+Donde el primer número a sumar es ''x'' y el segundo es ''sumatoria xs'', lo cual también es un número (aunque no lo parezca!): es el resultado de resolver la función ''sumatoria xs''.
 Entonces, la estructura común de todas estas funciones es:
+<code>
+fRecursiva :: [a] -> b
+fRecursiva [] = neutro
+fRecursiva (x:xs) = fNoRecursiva x (fRecursiva xs)
+</code>
-  _________ :: [a] -> b
+Observemos que hay dos diferencias principales con las aplicaciones y los filtros. Primero, tenemos un elemento más que debemos tratar con una variable y que por lo tanto tenemos que convertir en un argumento de la función: el neutro, que damos como resultado en el caso base. Segundo, la función que vamos a tomar como argumento es binaria, no unaria como en el caso de los filtros y las aplicaciones, por lo tanto, va a tener una estructura interna ligeramente distinta.
-  _________ []     = _____
-  _________ (x:xs) = _____ x (_________ xs)
+Por lo tanto, la generalización de los acumuladores quedaría como sigue:
+<code>
+acumula :: (a -> b -> b) -> b -> [a] -> b
+acumula f n []     = n
+acumula f n (x:xs) = f x (acumula f n xs)
+</code>
-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.
+Donde el primer argumento ''(a -> b -> b)'' es la función binaria que aplicamos en el caso recursivo, y el segundo argumento ''b'' es el neutro, que es el resultado que devolvemos en el caso base. Fíjense que usamos el mismo tipo para el resultado, el resultado de la función que aplicamos en el caso base y el neutro, ya que todos ellos tienen que convergir a un mismo tipo. El tipo de la lista inicial y el tipo que toma la función que aplicamos también tienen que coincidir, ya que si no no se podría aplicar la función a la lista, pero no tienen que coincidir necesariamente con el tipo del resultado, aunque pueden hacerlo.
-Por lo tanto, la generalización de los acumuladores es la siguiente:
+Ahora podemos escribir todas las funciones que son acumuladores mediante esta generalización.
+<code>
+sumatoria xs = acumular (+) 0 xs
+productoria xs = acumular (*) 1 xs
+concatenaInt xs = acumular (++) [] xs
+</code>
-  acumular :: (a -> b -> b) -> b -> [a] -> b
+==== Devolver una función como resultado ====
-  acumular f n []     = n
-  acumular f n (x:xs) =  f x (acumular f n xs)
-Ahora podemos escribir todas las funciones que son acumuladores mediante esta generalización.
+El alto orden nos permite no solamente tomar una función como argumento, sino también devolver una función como resultado. Esto resulta especialmente útil, porque nos permite usar funciones generales para definir funciones más concretas, concretando alguno de sus argumentos.
-  sumatoria xs = acumular (+) 0 xs
+Nosotros ya hemos visto algunos ejemplos de este uso con las generalizaciones ''multiplicar'' y ''porCiento''. Podemos pensar que ''multiplicar'' , con signatura de tipos ''multiplicar :: Int -> [Int] -> [Int]'', se puede leer de la siguiente forma:
-  productoria xs = acumular (*) 1 xs
+<code>
-  concatenaInt xs = acumular (++) [] xs
+multiplicar :: Int -> ( [Int] -> [Int] )
+</code>
+Y así la podemos usar para definir ''duplicar'':
+<code>
+duplicar :: [Int] -> [Int]
+duplicar = multiplicar 2
+</code>
+Fíjense que ''duplicar'' es justamente del tipo del resultado de ''multiplicar''.
-O bien aplicando secciones, es decir, sin escribir los argumentos obvios:
+Si una función no pudiera devolver como resultado otra función, no podríamos esperar que ''multiplicar 2'' fuera una definición suficiente para ''duplicar''.
-  sumatoria = acumular (+) 0
+===== Currificación =====
-  productoria = acumular (*) 1
-  concatenaInt = acumular (++) []
+Todo lo que hemos estado explicando hasta ahora sobre alto orden está fundamentado en un trabajo muy serio y sistemático sobre matemática y computación. Vamos a comentar brevemente lo que más toca al tema de alto orden, la //currificación//.
+Hace mucho mucho tiempo hubo un hombre llamado Haskell Curry que pensó mucho en las funciones y se le ocurrió pensar una función n-aria como una composición de n funciones unarias. La primera de estas funciones unarias toma como argumento el primer argumento de la función n-aria original y devuelve como resultado una función que toma como argumento el argumento el segundo argumento de la función n-aria original y devuelve como resultado una función que toma como argumento el tercer argumento de la función n-aria original... y así hasta que llegamos a una función que toma como argumento el último argumento de la función n-aria original y devuelve como resultado el resultado de la función n-aria original. Podríamos expresarlo así:
+<code>
+f :: a -> b -> c -> d -> f -> g
+>>>>>CURRIFICACIÓN>>>>>>>>>>>
+f :: a -> ( b -> ( c -> ( d -> ( f -> g ) ) ) )
+</code>
+Así en abstracto puede resultar difícil de entender. Veamos un ejemplo concreto. Tomemos como ejemplo la función ''porEncimaDe'', que, dado un entero ''n'', un entero ''m'' y una lista de enteros, devuelve solamente los enteros de la lista original que son mayores a ''m'' después de haberles restado ''n''. Su signatura de tipos es la siguiente:
+<code>
+porEncimaDe :: Int -> Int -> [Int] -> [Int]
+</code>
+La podemos currificar de la siguiente manera:
+<code>
+porEncimaDe :: Int -> ( Int -> [Int] -> [Int] )
+</code>
+Esto significa que la función tiene un argumento que es un entero y devuelve un resultado que es una función con el resto de argumentos, con signatura de tipos ''Int -> [Int] -> [Int]''. Intuitivamente, podemos pensarlo como que la función ''porEncimaDe'' busca primero un entero para luego tratar de resolver la función que queda. Después de haber encontrado el primer entero, lo que resta de la signatura de tipos también se currifica:
+<code>
+porEncimaDe :: Int -> ( Int -> ( [Int] -> [Int] ) )
+</code>
+Ahora, la función buscará otro entero, y luego se ocupará de resolver la función que queda, que busca una lista para devolver una lista. Esta forma de funcionar nos permite usar la función ''porEncimaDe'' concretando algunos de sus argumentos, en orden de currificación. Podemos escribir:
+<code>
+porEncimaDeRestando5 :: Int -> [Int] -> [Int]
+porEncimaDeRestando5 = porEncimaDe 5
+</code>
+O también
+<code>
+porEncimaDe20Restando5 :: [Int] -> [Int]
+porEncimaDe20Restando5 = porEncimaDe 5 20
+</code>
+En haskell se asume que todas las funciones están currificadas, así que internamente funcionan buscando primero el primer argumento, después el primer argumento del resto, y así sucesivamente.
+Si quieren saber más sobre el tema, pueden leer sobre [[http://en.wikipedia.org/wiki/Lambda_calculus|lambda cálculo]].
+===== Ejercicios para pensar =====
+==== Conexión entre dos ciudades ====
+Dada la siguiente base de conocimiento:
+<code>
+conectadas(rosario,buenosAires).
+conectadas(rosario,córdoba).
+conectadas(mendoza,córdoba).
+conectadas(rioNegro,santaCruz).
+conectadas(santaCruz,ushuaia).
+</code>
+Tratemos de averiguar si se puede ir de una ciudad a otra, es decir, si hay alguna conexión entre dos ciudades. Definimos el predicado ''hay_conexion/2'', que es recursivo:
+<code>
+hay_conexion(X,Y) :- conectadas(X,Y).
+hay_conexion(X,Y) :- conectadas(X,W) , hay_conexion(W,Y).
+</code>
+Ahora traten de ampliar esta función para que el intérprete nos diga el itinerario por el que hay que ir de una ciudad a otra. Otra posible ampliación es que el intérprete nos diga con qué medios de transporte podemos desplazarnos de una ciudad a otra; para que se pueda contestar a eso habrá que modificar los hechos.
+==== Recomendar amigos en una red social ====
+Este problema es complejo y por lo tanto se puede abordar de muy distintas formas. Acá les proponemos el principio de una, para que ustedes vayan trabajando en el problema. El próximo día vamos a ver algunas soluciones posibles para este problema.
+En primer lugar, pensemos qué información necesita nuestra función para trabajar. Primero de todo, necesita saber quién es la persona a quien vamos a recomendar nuevos amigos, y cuáles son los amigos que ya tiene. Luego necesita tener acceso a la base de datos en la que se guarda la información sobre todas las personas que están en la red social en cuestión. Por lo tanto, necesita dos argumentos: la persona y el listado de todas las personas.
+Cómo se representa la información sobre una persona en este problema? Hay muchas posibilidades. Yo les propongo la siguiente: una persona se representa como una tresupla donde el primer elemento es un entero que representa el número único de identificación de esa persona en la red social, el segundo elemento es un String que representa el nombre de la persona, y el tercer elemento es una lista de enteros que representa los identificadores de los amigos de esta persona en la red social. El resultado de la función podría ser un listado de nuevos amigos, representados por tuplas ''(String,Int)'' que representen al nombre y el identificador de los nuevos amigos. Así, la signatura de tipos de la función quedaría como sigue:
+<code>
+recomendarNuevosAmigos :: (Int,String,[Int]) -> [(Int,String,[Int])] -> [(String,Int)]
+</code>
+Ahora que sabemos con qué estructuras de datos vamos a trabajar, pensemos en lo que tenemos que hacer con ellas:
+  - obtener la lista de todos los amigos de los amigos de la persona a quien queremos recomendar nuevos amigos (llamémosle ''p''). Para eso necesitaremos la función ''losAmigosDeMisAmigos :: [Int] -> [(Int,String,[Int])] -> [Int]'', que se puede armar usando la función auxiliar ''listaDeAmigos :: Int -> [(Int,String,[Int])] -> [Int]''.
+  - descartar de esa lista todos los que ya son amigos de ''p'', es decir, que ya están en la lista de amigos de ''p''. Para eso necesitaremos la función ''filtrarNoEstanEnLista :: [Int] -> [Int] -> [Int]''.
+  - descartar de esa lista a ''p''.
+  - quedarnos solamente con los amigos que son amigos por lo menos de dos amigos de ''p'', es decir, descartar los que son amigos solamente de uno de los amigos de ''p''. Para eso necesitaremos el predicado ''existe2'', que se aplicará mediante un filtro.
+La función principal ''recomendarNuevosAmigos'' se puede definir ahora como una combinación de todas estas funciones auxiliares, por ejemplo, de la siguiente manera:
+<code>
+recomendarNuevosAmigos (id,n,misamigos) directorio = filter existe2 ( filter (noEs id) ( filtrarNoEstanEnLista misamigos ( losAmigosDeMisAmigos misamigos directorio ) ) )
+</code>
+===== Ejercicios =====
+  * Redefinan las funciones propuestas en los ejercicios de la clase anterior, ahora usando las generalizaciones ''filter'', ''map'' y ''foldr'', y no vuelvan a escribir ningún caso base ni caso recursivo más!
+  * Definan una función que calcule el porcentaje de estudiantes que aprobó o promocionó la materia, definiendo una función ''porcentajeEstudiantes :: (Int -> Bool) -> [(String,Int,Int,Int,Bool,Bool)] -> Int'', donde el primer argumento es un predicado que determina si una nota aprueba o desaprueba o si una nota promociona o no promociona, el segundo argumento es la lista de estudiantes, representados como seis-uplas con su nombre, la nota de cada uno de los tres parciales y dos booleanos que representan la aprobación o desaprobación de cada uno de los parcialitos de taller. El resultado es el porcentaje de estudiantes que aprobaron o promocionaron la materia, dependiendo del predicado que pongamos como primer argumento.
+  * Definan una función que determine si Clara es mayor que Elena, dada la siguiente base de conocimiento:
+<code>
+mayor(clara,esteban).
+mayor(esteban,paula).
+mayor(paula,marcos).
+mayor(marcos,elena).
+</code>