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.
====== Clase 5 ======



===== Tratando funciones más complejas =====

Como vimos en los ejercicios de la clase anterior, en muchos casos las funciones que queremos hacer no son casos "puros" de alguna de las tres generalizaciones, sino que para solucionarlas debemos dar un giro de tuerca más. Vamos a ver dos estrategias distintas. 

La primera estrategia está basada en la técnica de "divide y vencerás", también conocida como modularización, en la que dividimos el problema en partes más chicas que solucionamos por separado y finalmente unimos para obtener la solución total. 

La segunda estrategia consiste en complejizar las funciones con las que trabajamos en las generalizaciones, especialmente en los acumuladores.

Muchos problemas se pueden enfocar con ambas estrategias, aunque algunos sólo admiten una de ellas.

==== Divide y Vencerás ====

Veamos la función //longitud//((La función //longitud// viene ya definida en el preámbulo como //length//, pero acá la vamos a volver a definir para ver cómo funciona.)), que cuenta cuántos elementos tiene una lista. Podríamos definirla así:

  longitud :: [a] -> Int
  longitud xs = foldr (+) 0 xs

Pero esta función no anda! ¿por qué? porque el operador //+// requiere que sus argumentos sean números, y la declaración de tipos de //longitud// no nos garantiza que la lista sea de números. Por lo tanto, habrá que garantizarlo de alguna forma: convirtiendo los elementos de la lista a números. Y además, no sólo queremos convertirlos a números, queremos convertirlos de forma que se cuente 1 por cada elemento de la lista, así que vamos a tener que convertir todos los elementos en 1. Sabemos todo esto, pero cómo lo hacemos?

Para darnos cuenta de qué funciones hay que combinar y cómo hay que hacerlo, podemos pensar intuitivamente en lo que hay que hacer para resolver la tarea que se propone en la función, paso a paso. En primer lugar, habrá que convertir todos los elementos de la lista en 1, en segundo lugar, habrá que sumar todos esos 1 para llegar a un número que será el total de elementos.

Entonces, empecemos por crear una función que toma un elemento cualquiera y devuelve el valor constante 1:

  sea1 :: a -> Int
  sea1 x = 1

Ahora lo que tenemos que hacer es aplicar esta función a nuestra lista, mediante la función que generaliza la aplicación, //aplica// (o //map// si usamos la que viene definida en el preámbulo):

  convierte1 :: [a] -> [Int]
  convierte1 xs = map sea1 xs

Una vez tenemos la lista convertida en números, hay que sumarlos, usando un acumulador (la función //foldr// si usamos la que viene definida en el preámbulo):

  longitud :: [a] -> Int
  longitud xs = foldr (+) 0 (convierte1 xs)

o bien, reemplazando //convierte1// por su definición:

  longitud xs = foldr (+) 0 (map sea1 xs)

Veamos otro ejemplo: la función //cuantosCumplen//, que dado un predicado //p// y una lista //xs//, nos devuelve un número que indica cuántos elementos de la lista cumplen con //p//. Como vemos, la forma externa de esta función es un acumulador, ya que toma una lista pero no devuelve una lista sino un valor. Sin embargo, no aplicamos una función a toda la lista sin más, sino sólo a los elementos que cumplen con el predicado, lo cual parece claramente un filtro . Por lo tanto, parece claro que en esta función habrá que combinar un filtro y un acumulador.

Pensemos en lo que hay que hacer para resolver la tarea que se propone en la función, paso a paso. Primero queremos filtrar los elementos que cumplen con el predicado, y luego contar cuántos son. Bien, entonces lo hagamos paso por paso: primero, filtremos los elementos que cumplen con el predicado. Esta función es un filtro, por lo tanto la escribiremos como tal (usando la función //filter// del preámbulo):

  filtraCuantosCumplen :: (a -> Bool) -> [a] -> [a]
  filtraCuantosCumplen p xs = filter p xs

Esta función //filtraCuantosCumplen// nos devolverá una lista que contiene únicamente los elementos de la lista original que cumplen con el predicado //p//. Ahora necesitamos contar cuántos son estos elementos. Para eso podemos aplicar la función //longitud// que hemos visto arriba, o volver a definirla:

  cuenta :: [a] -> Int
  cuenta xs = foldr (+) 0 (map sea1 xs)

La función //cuantosCumplen// combinará estas dos funciones para obtener su resultado:

  cuantosCumplen :: (a -> Bool) -> [a] -> Int
  cuantosCumplen p xs = cuenta ( filtraCuantosCumplen p xs )

O también lo podemos escribir así:

  cuantosCumplen' :: (a -> Bool) -> [a] -> Int
  cuantosCumplen' p xs = foldr (+) 0 ( map sea1 (filter p xs) )

Como ven, la estrategia //divide y vencerás// desmenuza el problema en pasos chiquitos, que tratamos por separado, **comprobamos que cada paso hace lo que esperamos que haga**, y los combinamos a todos para obtener el resultado final.

==== Poniendo el peso en la función ====

Otra forma de enfocar un problema complejo es haciendo más compleja la función que se aplica a la lista. Esta aproximación es más propia del paradigma de programación funcional y es especialmente útil en el caso de los acumuladores. Veamos cómo se trataría de esta forma la función //longitud//. 

En el apartado anterior habíamos visto cómo convertíamos primero la lista en una lista de 1, y luego sumábamos todos los 1. Ahora la misma función que suma nos va a convertir a los elementos en 1. Cómo sería una función así? Recordemos además que debe tener la estructura de tipos que la haga compatible con //foldr//:

  foldr :: (a -> b -> b) -> [a] -> b

Recuerden cómo se aplica la función de foldr, en el paso recursivo:

  foldr f n (x:xs) = f x (foldr f n xs)

La función toma dos argumentos: uno que es la cabeza de la lista y otro que es el **resultado** de aplicar el acumulador al resto de la lista.

Por lo tanto, la función que buscamos deberá tener el tipo //(a -> b -> b)//, y sumar 1 por cada elemento de la lista, y con la forma que acabamos de ver, sumando 1 por la cabeza al resultado de sumar el resto de la lista:

  suma1 :: a -> b -> b
  suma1 x y = 1 + y

En //suma1//, //x// sería el argumento que pasamos como cabeza de la lista y //y// sería el resultado de sumar el resto de la lista.

Una vez tenemos la función definida, la incorporamos a la función recursiva global:

  longitud' :: [a] -> Int
  longitud' xs = foldr suma1 0 xs

Si desglosamos esta definición, trasladándola a la estructura de foldr, con caso base y caso recursivo, quedaría así:

  longitud'' :: [a] -> Int
  longitud'' []     = 0
  longitud'' (x:xs) = 1 + (longitud'' xs)

Pero por supuesto, ahora que ya dominamos las funciones generalizadas (map, filter, foldr), no queremos escribir más casos base y casos recursivos.

Otro buen ejemplo de complejización de la función que aplicamos a la lista es el de la función //reversa//, que nos da una lista con sus elementos al revés (primero el último, segundo el anteúltimo, etc.). Esta función es un acumulador, aunque nos dé una lista como resultado; esta lista debe verse como un valor, y no como el resultado de una aplicación. 

Para ayudar a pensar esta función, que es bastante complicada, vamos a dar primero su definición con caso base y caso recursivo:

  reversa :: [a] -> [a]
  reversa []     = []
  reversa (x:xs) = (reversa xs) ++ [x]

De esta forma, los elementos se van colocando al final de la lista: el primero se coloca el último, el segundo el penúltimo, etc. Usamos el operador ++ porque el operador : no se puede usar a la derecha de una lista. 

La función que trata este problema deberá hacer lo mismo. Esta función debe tener tipo //a -> b -> b//, ya que es la función de un acumulador. Pero sabemos que //b// es el tipo del resultado, y sabemos que el resultado de //reversa// es //[ a ]//, así que vamos a concretarlo así:

  alacola :: a -> [a] -> [a]
  alacola x y = y ++ [x]

En esta función, la variable //y// es una lista, y la variable //x// es la cabeza de la lista. Ahora que ya tenemos la función, sencillamente, la ponemos en su lugar en el acumulador:

  reversa' :: [a] -> [a]
  reversa' xs = foldr alacola [] xs

Para practicar el tratamiento de casos complejos, recomendamos los ejercicios de la clase anterior, que copiamos en la sección de ejercicios.




===== Recursión en dos argumentos =====

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.

=====Ejercicios=====

===Ejercicios de funciones complejas===

  * Definir la función //cuantosCumplen//, //cuantosCumplen :: (a -> Bool) -> [a] -> 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//, //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//, //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//, //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//, //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//, //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//, //edadPromedio:: [(String,Int)] -> Int//, que dada una lista de pares //(nombre,edad)//, retorna el promedio de edad de las personas.

===Ejercicios de recursión en dos argumentos===

  * 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:
<code>
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")]
</code>