Ciencias de la Computación FAMAF

En la clase anterior aprendimos cómo generalizar los programas que habíamos visto hasta el momento mediante dos estrategias básicas: generalización de tipos y generalización de funciones. Recordemos brevemente estas dos formas de generalización a través de un par de ejemplos.

Aquí vemos dos funciones muy parecidas, dado un elemento y una lista de elementos, estas funciones seleccionan los elementos de una lista que son idénticos al elemento que les damos de entrada; la primera funciona con letras y la segunda con números (Ejemplo: esLetra 's' ['s','o','n','s','o'] = ['s','s'] ; esNumero 3 [4,3,2,6,7] = [3]).

esLetra :: Char -> [Char] -> [Char]
esLetra l []     = []
esLetra l (x:xs) | x == l = x : esLetra l xs
                 | x /= l =     esLetra l xs

esNumero :: Int -> [Int] -> [Int]
esNumero n []     = []
esNumero n (x:xs) | x == n = x : esNumero n xs
                  | x /= n =     esNumero n xs

¿Cómo podemos generalizar estas dos funciones en una sola? La única diferencia que hay entre ellas son los tipos que manejan. Podemos abstraernos de los tipos y crear una función que devuelva los elementos idénticos a un elemento de una lista de elementos de cualquier tipo, de la siguiente forma:

es :: Eq a => a -> [a] -> [a]
es x []     = []
es x (y:ys) | x == y = y : es x ys
            | x /= y =     es x ys

Las funciones que pueden tratar diferentes tipos se llaman funciones polimórficas. Cada variable de tipo puede denotar cualquier tipo, pero variables idénticas denotan tipos idénticos, y letras distintas pueden denotar el mismo tipo o tipos distintos. Por ejemplo, si “a” es Char, entonces todas las “a” de la definición de tipos de la función tienen que ser Char. Si tenemos una “b”, “b” puede ser Char, Int, Bool, [a], etc., pero tendrá que ser del mismo tipo que cualquier otro “b” que haya en la definición de tipos de la función.

Con Eq a ⇒ definimos una restricción de tipo, marcando que “a puede ser qualquier tipo mientras tenga == igualdad”. Más adelante lo utilizaremos nuevamente.

En la clase anterior vimos cómo podíamos obtener funciones generales que llevaran a cabo los tres grandes tipos de operaciones recursivas en listas: aplicación, filtro y acumulación. Si además aplicamos abstracción de tipos, podemos definir las funciones más específicas instanciando o bien los tipos o bien los parámetros de estas funciones más generales.

Las aplicaciones toman como argumentos una función “f” y una lista, aplican la función a cada uno de los elementos de la lista y devuelven una lista con los valores resultantes de la aplicación de la función a cada uno de los elementos de la lista. La función “f” tiene que tomar como argumento necesariamente elementos del mismo tipo que la lista que le damos como argumento a la función recursiva aplicación, y tiene que devolver como resultado necesariamente elementos del mismo tipo que la lista que devuelve la función recursiva aplicación. La lista de argumento y de resultado pueden ser del mismo tipo pero no es necesario.

mapa :: (a -> b) -> [a] -> [b]
mapa f []     = []
mapa f (x:xs) = f x : mapa f xs 

En el preludio, se llama map y se define así:

map              :: (a -> b) -> [a] -> [b]
map f xs          = [ f x | x <- xs ]

Esta notación se denomina listas por comprensión y se puede estudiar en la sección 2.4.1 de Una introducción agradable a Haskell.

Los filtros toman como argumento una función “p” y una lista. La función “p” tiene la particularidad de ser un predicado, es decir, una función que devuelve un valor booleano. Los filtros devuelven como resultado todos aquellos elementos de la lista que devuelven True para la función “p”, o lo que es lo mismo, se descartan los elementos que devuelven False para la función “p”. La función “p” tiene que tomar como argumentos elementos del mismo tipo que la lista de argumento de la función recursiva filtro. La lista de resultado de la función recursiva filtro tiene que ser del mismo tipo que la lista de argumento.

filtro :: (a -> Bool) -> [a] -> [a]
filtro p []     = []
filtro p (x:xs) | p x       = x : filtro p xs
                | not (p x) =     filtro p xs

En el preludio se llama filter y también se define utilizando listas por comprensión.

filter           :: (a -> Bool) -> [a] -> [a]
filter p xs       = [ x | x <- xs, p x ]

Las acumulaciones toman un argumento más que las aplicaciones y los filtros, porque hay que especificar el resultado que se devuelve en el caso base, que es el neutro de la función “f” que usemos para ir acumulando el resultado.

En las aplicaciones y los filtros, como el resultado es una lista, el neutro viene determinado por el resultado. Como sabemos que el resultado es una lista, el operador que usamos para ir acumulando el resultado es el constructor de listas (:), y en el caso base se devuelve el neutro del constructor de listas, la lista vacía [].

En las acumulaciones no sólo la función “f”, sino también el neutro se tiene que especificar como argumentos. Vemos que la función “f” toma dos argumentos: uno de ellos será la cabeza de la lista en ese momento de procesamiento, el otro, el resultado que eventualmente obtendremos de aplicar la función recursiva de acumulación al resto de la lista. Por esta razón el resultado de la función recursiva de acumulación debe ser necesariamente del mismo tipo que el segundo argumento de la función “f”, que será el mismo tipo que el del resultado de “f”. En cambio, los elementos de la lista que toma la función recursiva como argumento pueden ser de otro tipo. Veamos la definición:

acumula ::  (a -> b -> b) -> b -> [a] -> b
acumula f n [] = n 
acumula f n (x:xs) = f x (acumula f n xs)

Para entender bien el sentido que tiene dar el neutro como un argumento, vean qué pasa si intentan definir la productoria con la siguiente definición de aplicación, que tiene un “símil de neutro” incorporado a su definición:

acumularTrucho ::  (a -> b -> b) -> [a] -> b
acumularTrucho f [] = 0
acumularTrucho f (x:xs) = f x (acumularTrucho f xs)

En el Preludio se llama foldr y se define así:

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr f z []      = z
foldr f z (x:xs)  = f x (foldr f z xs)

En el Preludio se usa, por ejemplo, para definir las funciones concat, and y or:

concat           :: [[a]] -> [a]
concat     = foldr (++) []

and, or   :: [Bool] -> Bool
and        = foldr (&&) True
or         = foldr (||) False

• Utilizando aplicaciones, filtros y/o acumuladores, definir las funciones paraTodo, existe:: (a→Bool) → [a] → Bool, donde paraTodo.p.xs decide si el predicado p es válido para todos los elementos de xs. Idem para existe, sólo que la cuantificación es existencial (“hay alguno que satisface p”). Ejemplos: paraTodo.(>0).[3,6,0,9] = False, existe.(=='a').“Maniobra” = True.
• ¿Cuáles son el paraTodo y existe del preámbulo estandar? Revisar su definición.

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.

• 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")]

Veamos un ejercicio un poco más complejo. Imaginemos que estamos trabajando en Google, en el equipo que trabaja con el algoritmo PageRank, que determina la relevancia de una determinada página web. Tenemos un archivo con una lista de pares de urls, donde (u1,u2) está en la lista sii la página u1 apunta a la u2. En el archivo de texto webGraph.txt están las urls están separadas por el símbolo “|”.

   http://arcadia.homelinux.org/~emilio/wordpress/archives/133|http://www.eeuskadi.net
   http://arn.espora.org/article.pl?sid=05/07/27/0016205|http://www.eeuskadi.net
   http://encuestas.lagateradigital.com/|http://www.lagateradigital.com/
   http://encuestas.lagateradigital.com/|http://www.lagateradigital.com/intenciones.php#donar
   http://familydoctor.org/e197.xml|http://www.aafp.org

Este archivo es una parte del grafo de la web o webGraph como lo llamaremos de aquí en adelante.

Lo primero que vamos a querer es cargarlo en memoria para poder extraer información relevante. Para ello necesitamos importar una biblioteca especial que nos permite leer información de archivos, y efectivamente importar la información del archivo:

-- extensión para poder leer archivos en Strings
import Hugs.IOExts(unsafePerformIO)

-- constante principal con el grafo de la web.
webGraph :: [(String,String)]
webGraph = parseWebGraph (leeArchivo "webGraph.txt")

-- carga un archivo en un String, usa IOExts
leeArchivo :: String -> String
leeArchivo nombre = unsafePerformIO $ readFile nombre

-- transforma el contenido del archivo de String a lista de tuplas
parseWebGraph :: String -> [(String,String)]
parseWebGraph [] = []
parseWebGraph xs = (fuente,destino) : parseWebGraph resto
   where
        fuente = takeWhile (not.esSeparador) xs
        todoMenosFuente = dropWhile esSeparador (dropWhile (not.esSeparador) xs)
        destino = takeWhile (not.esFinLinea) todoMenosFuente
        resto = dropWhile esFinLinea (dropWhile (not.esFinLinea) todoMenosFuente)

esSeparador,esFinLinea :: Char -> Bool
esSeparador x = elem x "| "
esFinLinea  x = elem x "\n\r"

Nuestro archivo es razonablemente pequeño y vamos a hacer procesamiento razonablemente pequeño con él, pero si estamos tratando con toda la web, tendremos que manejar millones de urls y hacer procesamiento bien costoso con ellas. Para ello tendremos que aplicar una estrategia de Divide y conquista. En Google existe un modelo de programación llamado MapReduce que proporciona una forma de dividir un gran volumen de trabajo en pedazos más chicos, enviarlo a diferentes computadoras que hacen cada uno de estos pedazos y después unirlos de vuelta.

Por ejemplo podemos obtener la cantidad de aristas o enlaces del grafo:

Main> length webGraph
4852

O las primeras 32 urls fuente:

Main> take 32 (map fst webGraph)
["http://ana-gabriel.letras.terra.com.br/letras/168154/","http://ana-gabriel.letras.terra.com.br/letras/168154/","http://ana-gabriel.lyrics-songs.com/lyrics/168154/"

Vamos a desarrollar diferentes funciones para obtener información de esta lista.

• Determinar cuales y cuantas páginas se apuntan a si mismas.
• Para los siguientes puntos necesitaremos definir un par de funciones auxiliares:
  • primeros :: [(a,b)] → [a] y segundos :: [(a,b)] → [b] que le toman la primera y segunda coordenada a cada elemento de la lista de pares. Sirve para obtener todas las urls fuente y destino respectivamente. Ayuda: con map alcanza.
  • concatenaPares :: [(a,a)] → [a] que devuelve la concatenación de todos los pares de la lista. Sirve para obtener una lista “plana” de los urls. Observación: se puede hacer una definición recursiva o bien utilizar las anteriores y ++.
• Ahora queremos saber si un determinado url está en nuestro modelo simplificado y acotado de la web. La función que nos determina si un elemento está o no está en una lista es un acumulador, ya que parte de una lista y nos devuelve un valor (booleano), más en concreto el acumulador elemento :: Eq a ⇒ a → [a] → Bool. En el preámbulo hay una función que devuelve True si un elemento dado está en una lista, cuál es? Si no la encontramos podemos definirla utilizando existe.
• ¿Cómo podemos saber cuántas veces ocurre una determinada página? y cómo podemos distinguir entre cuántas veces en todo el archivo, cuántas veces apuntando, cuántas veces apuntada? Definir cuantas :: Eq a ⇒ a → [a] → Int, donde cuantas x xs que determina la cantidad de veces que ocurre x en xs. Utilizar esto junto a primeros, segundos y concatenaPares para lograr el objetivo.
• ¿Cómo podemos saber a qué páginas apunta una determinada página? aCualesApunta :: Eq a ⇒ a → [(a,b)] → [b] y ¿Cómo podemos saber qué páginas apuntan a una determinada página? cualesApuntan :: Eq b ⇒ b → [(a,b)] → [a]. Ayuda: sale con filter y algo más.
• ¿Cómo podemos saber a cuántas páginas web distintas apunta una determinada página? Ayuda: usar la función length y alguna otra que hayamos definido antes. acuantasApunta :: Eq a ⇒ a → [(a,b)] → Int
• ¿Cómo podemos saber cuántas páginas web distintas apuntan a una determinada página? cuantasApuntan :: Eq b ⇒ b → [(a,b)] → Int.

Por último, de cara al futuro o a la próxima clase, podemos pensar cómo aplicaríamos estas funciones (que ahora aplicamos a una sola url) a todas las urls de la lista, recursivamente, por ejemplo, cómo podríamos obtener funciones que nos den la cantidad de urls a las que apunta cada url, de forma que luego podamos ordenar de la url que apunta a más urls a las que apuntan a menos.