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 veremos más ejemplos.

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 solo que la cuantificación es existencial (“hay alguno que satisface p”).

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' (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. Estas dos listas están ordenadas de menor a mayor. Lo que queremos es encontrar personas que estén en las dos listas. Podemos hacerlo de una forma muy poco eficiente:

No decir que son listas ordenadas.

encuentraEstafador :: [Int] -> [Int] -> [Int]
encuentraEstafador [] _      = []
encuentraEstafador (x:xs) ys | any (==x) ys = x : encuentraEstafador xs ys
                             | otherwise    =   : encuentraEstafador xs ys

La función any se encuentra en el preámbulo y tiene la siguiente definición:

any :: (a -> Bool) -> [a] -> Bool
any p = or  . map p

También podríamos usar la función elem, con la siguiente definición:

elem :: Eq a => a -> [a] -> Bool
elem = any . (==)

Esta versión es poco eficiente porque para cada elemento de la primera lista tenemos que recorrer toda la segunda lista. Sin embargo, como sabemos que las listas están ordenadas, podríamos aprovechar este hecho para recorrerlas a ambas de forma más eficiente.

Aca ejercicio de encuentraEstafador con listas ordenadas.

Como se ve por la especificación de tipos de encuentraEstafador, tenemos que trabajar con listas de números, idealmente, su número de DNI. Pero normalmente, si pedimos listados de personas, nos devolverán más datos que únicamente su número de DNI: también nos devolverán el número, posiblemente la fecha de nacimiento, su tipo de contrato, etc. Ahora supongamos que la lista de personas que reciben el subsidio de desempleo está formada por tuplas (dni,nombre,mesesDeDesempleo), con los siguientes tipos: (Int,String,Int). En la lista 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). Con estas listas, habrá que hacer un pequeño preproceso para poder aplicar la función encuentraEstafador: hay que quedarse únicamente con los números de DNI. Para ello habrá que hacer dos funciones: una transformaDesempleo :: [(Int,String,Int)] → [Int] y otra transformaMunicipalidad :: [(String,Int,String)] → [Int]. Aunque también podemos usar una función más general, politípica, que nos sirva para recuperar el primer, segundo, tercer elemento de una tupla con tipos cualquiera, como las funciones fst y snd que encontramos en el preludio:

Pondría [(dni,Nombre)] y [(nombre,dni)] para poder usar fst y snd. Les daría un caso concreto definiendo dos constantes listadoSubsidio y listadoMunicipales para que prueben También metería un ejercicio que sea esto, usar encuentraEstafador a partir de fst,snd y map.

fst            :: (a,b) -> a
fst (x,_)       = x

snd            :: (a,b) -> b
snd (_,y)       = y

Ahora supongamos que estas listas no están ordenadas por DNI, sino por nombre. En ese caso, una vez obtuvimos la lista de DNIs, tenemos que ordenarlas para poder aplicar en algoritmo eficiente (encuentraEstafador') con garantía de éxito; recordemos que es esencial para que funcione este algoritmo que las listas estén ordenadas. Por lo tanto, habría que hacer (o encontrar hecha!) una función ordenar.

No me metería con “ordenar antes”, luego aplicar, porque ya no tiene tanto sentido la eficienca de encuentraEstafador' .

Teniendo en cuenta todos estos añadidos, cómo podríamos componer una función encuentraEstafador' que extraiga los elementos adecuados de cada una de las tuplas, los ordene y los pase como argumentos a encuentraEstafador'?

Vean que la función resultante puede quedar bien sencilla de leer justamente porque estamos usando otras funciones que hemos definido antes o que se encuentran definidas en el preludio. Nuestro objetivo para problemas complejos será identificar las subpartes de un problema que se pueden aislar y tratar en una función separada, a ser posible una función que ya haya sido definida y no tengamos que volver a definir.

Aca mostraría eficiencia con :set +s y el número de reducciones

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 IOExts

-- 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 = drop 1 (dropWhile (not.esSeparador) xs)
        destino = takeWhile (not.esFinLinea) todoMenosFuente
        resto = drop 1 (dropWhile (not.esFinLinea) todoMenosFuente)

esSeparador,esFinLinea :: Char -> Bool
esSeparador x = x=='|'
esFinLinea  x = x=='\n'

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.

• Antes que nada necesitamos 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 :: 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. : reescribir
  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. ===== Ejercicios ===== ==== Generalización ==== Generalizar las siguientes funciones usando las definiciones de aplicacion, filtro y acumular, aplicando generalización de tipos si es necesario: === Aplicación === * duplica * multiplica * veintePorCiento * nPorciento === Filtro === * empiezaM * solo0y1 * filtraNumeros === Acumulación === * sumatoria * productoria * factorial * contador * todos0y1 * paraTodo * existe ==== Funciones mixtas ==== * Definir la función edadReal: [(String,String,Int,Bool)] → [(String,Int)], que toma una lista de cuatruplas con la siguiente información sobre personas: nombre de la persona, sexo, edad y si está mintiendo en la edad o no, y devuelve una lista de tuplas con el nombre y la edad de cada persona, de forma que si es una mujer que miente sobre su edad (tiene “True” en el cuarto elemento de la cuatrupla) se le suma 5 a la edad de la cuatrupla, y si es un hombre, se le resta 5. Ejemplo: edadReal [ (“Ana”,“M”,45,False), (“Pedro”,“H”,30,False), (“Teresa”,“M”,35,True), (“Esteban”,“H”,40,False) ] = [ (“Ana”,45), (“Pedro”,30), (“Teresa”,45), (“Esteban”,35) ] * Definir la función escalaImpuesto: [(String,Int)] → [(String,Int)], que toma una lista de tuplas con el nombre de un usuario y su gasto mensual de electricidad, y devuelve una lista de tuplas con el nombre de aquellos usuarios que gastan más de 50 pesos mensuales de electricidad y su gasto multiplicado por 3. Esta función se puede usar para recalcular el impuesto a pagar por los usuarios que más gastan. Ejemplo: escalaImpuesto [(“Perez”,30), (“Gomez”,67), (“Martinez”,55), (“Rodriguez”,24)] = [(“Gomez”,201),(“Rodriguez”,72)]