Ciencias de la Computación FAMAF

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== Generalización de funciones recursivas y alto orden ======

===== Generalización =====

En esta clase vamos a ver las funciones recursivas en listas con algo más de abstracción. Ya vimos que los diferentes tipos de funciones comparten una estructura común, con algunas muy pequeñas variaciones (el predicado que se filtra, la función que se aplica, el operador con el que se acumula). Veremos que en haskell podemos hacer que estas pequeñas variaciones sean un parámetro más de la función. De esta forma vamos a poder generalizar todavía más. Por ejemplo, vamos a crear una función ''filtro'' donde el predicado con el que filtramos sea un argumento más de la función. Esto nos va a servir para poder escribir todas las funciones de tipo filtro de forma mucho más concisa.

Este proceso de generalización es muy parecido al proceso que hicimos al definir la función ''multiplicar :: Int -> [Int] -> [Int]'' como generalización de ''duplicar :: [Int] -> [Int]'', ''triplicar :: [Int] -> [Int]'', etc: encontramos que había algo dentro de las funciones ''duplicar'' y ''triplicar'' que se podía tratar como una variable, y que en ese caso las dos funciones eran idénticas. El valor de esta variable pasaba a ser uno de los argumentos requeridos de la función, el que hemos puesto como primer argumento de ''multiplicar''. Así, se puede definir:
<code>
duplicar xs = multiplicar 2 xs
triplicar xs = multiplicar 3 xs
</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. 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. 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.

==== Tomar una función como argumento ====

=== Aplicaciones (map) ===

¿No estamos ya cansados de escribir siempre lo mismo?
Las funciones de //tipo aplicación//, son todas idénticas, salvo por la **operación o función** que se aplica a cada elemento.

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

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

Entonces generalicemos. Podemos definir una función general para cualquier aplicación, donde la operación que se aplica a cada uno de los elementos de la lista viene dada como un argumento más de la función. Esto es, definimos una función (la función //aplicación//) que toma como parámetro a otra función (la operación que se aplica a cada elemento de la lista). Así, podremos cambiar lo que hace la función aplicación de forma muy sencilla, cambiando esta segunda función cada vez que llamemos a la función aplicación. 

La forma generalizada de las funciones de aplicación se compone de lo que tienen en común todas las funciones aplicación que hemos visto hasta ahora:
<code>
fRecursiva :: [a] -> [b]
fRecursiva []     = []
fRecursiva (x:xs) = fNoRecursiva x : fRecursiva xs
</code>

Ahora lo que queremos hacer es que ''fNoRecursiva'' sea un argumento más de ''fRecursiva''. Para eso hay que cambiar la signatura de tipos, incorporando este nuevo argumento. Llamemos ''aplica'' a esta nueva ''fRecursiva''.
<code>
aplica :: (a -> b) -> [a] -> [b]
</code>

Vemos que la nueva función tiene un nuevo argumento, ''a -> b''. Sabemos que este argumento es una función porque es complejo: toma un elemento de tipo ''a'' y devuelve un elemento de tipo ''b''. Esta función será precisamente la función que aplicaremos a cada uno de los elementos de la lista, ya sea //multiplicar por dos//, //transformar a binario//, o cualquier otra. Entonces, la función ''aplica'' combinará esta nueva signatura de tipos con el esquema general de las aplicaciones, donde ahora la función que se aplica es uno de los argumentos de la función. Quedará definida de la siguiente forma:
<code>
aplica :: (a -> b) -> [a] -> [b]
aplica f [] = []
aplica f (x:xs) = f x : aplica f xs
</code>

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 xs = aplica (*2) xs
veintePorCiento :: [Float] -> [Float]
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) ===

Veamos funciones de //tipo filtro// que hemos creado:

<code>
esPar :: Int -> Bool
esPar = esDivisor 2

soloPares :: [Int] -> [Int]
soloPares [] = []
soloPares (x:xs) | esPar x   =  x : soloPares xs
                 | otherwise =      soloPares xs
</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
</code>

¿Cuál es la estructura que tienen en común estas funciones?
<code>
fRecursiva :: [a] -> [a]
fRecursiva [] = []
fRecursiva (x:xs) | predicado x  =  x : fRecursiva xs
                  | otherwise    =      fRecursiva xs
</code>

A esta base común hay que añadir un argumento más: la función que se va a evaluar para todos los elementos de la lista. Este tipo de función es un **predicado**, es decir una función que devuelve un booleano, que decidirá si cada elemento se conserva o se filtra. En el ejemplo anterior, el predicado era primeraEsM, pero en el caso generalizado no lo vamos a especificar en la función sino que vamos a pedir que nos venga dado como un argumento más cuando se llama a la función.
<code>
filtrar :: (a -> Bool) -> [a] -> [a]
filtrar p []     = []
filtrar p (x:xs) | p x       = x : filtrar p xs
                 | otherwise =     filtrar p xs
</code>

De esta forma, llamando a la función general con diferentes operaciones como argumento, podremos definir las diferentes funciones que hemos visto hasta ahora, por ejemplo:
<code>
soloPares xs = filtrar esPar xs
empiezaM xs = filtrar primeraEsM xs
</code>

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) ===

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

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

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

productoria :: [Int] -> Int
productoria []     = 1
productoria (x:xs) = producto x (productoria xs)
</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. 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'', 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>

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.

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>

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. 

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>

==== Devolver una función como resultado ====

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. 

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:
<code>
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''.

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''.

===== Currificación =====

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>