Ciencias de la Computación FAMAF

Herramientas de usuario

Herramientas del sitio

Traza:
introalg:taller07_5

Diferencias

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

Enlace a la vista de comparación

Ambos lados, revisión anteriorRevisión previa
Próxima revisión		Revisión previa
introalg:taller07_5 [2007/05/28 16:19] – nicolaswintroalg:taller07_5 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
Línea 2: Línea 2:
  
 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. 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.
 +
  
  
Línea 21: Línea 22:
 </code> </code>
  
-?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:+¿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:
  
 <code> <code>
Línea 32: Línea 33:
 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. 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.+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. 
 + 
  
  
Línea 95: Línea 98:
   foldr f z (x:xs)  = f x (foldr f z xs)   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":+En el Preludio se usa, por ejemplo, para definir las funciones ''concat'', ''and'' y ''or'':
  
   concat           :: [[a]] -> [a]   concat           :: [[a]] -> [a]
Línea 104: Línea 107:
   or         = foldr (||) False   or         = foldr (||) False
  
-FIXME + 
-?Aprovechar y que definian ''paraTodo, existe:: (a->Bool) -> [a] -> Bool'' con acumula y/o con map y and/or? + 
-Y de paso practican lo del teórico!+ 
 +==== Ejercicios ==== 
 + 
 +  * 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. 
 + 
 + 
  
  
Línea 124: Línea 134:
 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: 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' (x:xs) (y:ys) = (x,y) : abrochar xs ys
   abrochar' _ _ = []   abrochar' _ _ = []
Línea 136: Línea 147:
 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. 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: +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:
- +
-FIXME +
-No decir que son listas ordenadas.+
  
   encuentraEstafador :: [Int] -> [Int] -> [Int]   encuentraEstafador :: [Int] -> [Int] -> [Int]
   encuentraEstafador [] _      = []   encuentraEstafador [] _      = []
-  encuentraEstafador (x:xs) ys | any (==x) ys = x : encuentraEstafador xs ys +  encuentraEstafador (x:xs) ys | existe (==x) ys = x : encuentraEstafador xs ys 
-                               | otherwise    =   : encuentraEstafador xs ys+                               | otherwise       =     encuentraEstafador xs ys
  
-La función //any// se encuentra en el preámbulo y tiene la siguiente definición: +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.
- +
-  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. +
- +
-FIXME +
-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: +
- +
-FIXME +
-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//. +
- +
-FIXME +
-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. +
- +
-FIXME +
-Aca mostraría eficiencia con '':set +s'' y el número de reducciones+
  
  
 +====Ejercicios====
  
 +  * 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>
  
  
Línea 212: Línea 191:
 <code> <code>
 -- extensión para poder leer archivos en Strings -- extensión para poder leer archivos en Strings
-import IOExts+import Hugs.IOExts(unsafePerformIO)
  
 -- constante principal con el grafo de la web. -- constante principal con el grafo de la web.
Línea 220: Línea 199:
 -- carga un archivo en un String, usa IOExts -- carga un archivo en un String, usa IOExts
 leeArchivo :: String -> String leeArchivo :: String -> String
-leeArchivo nombre = unsafePerformIO$ readFile nombre+leeArchivo nombre = unsafePerformIO $ readFile nombre
  
 -- transforma el contenido del archivo de String a lista de tuplas -- transforma el contenido del archivo de String a lista de tuplas
Línea 228: Línea 207:
    where    where
         fuente = takeWhile (not.esSeparador) xs         fuente = takeWhile (not.esSeparador) xs
-        todoMenosFuente = drop 1 (dropWhile (not.esSeparador) xs)+        todoMenosFuente = dropWhile esSeparador (dropWhile (not.esSeparador) xs)
         destino = takeWhile (not.esFinLinea) todoMenosFuente         destino = takeWhile (not.esFinLinea) todoMenosFuente
-        resto = drop 1 (dropWhile (not.esFinLinea) todoMenosFuente)+        resto = dropWhile esFinLinea (dropWhile (not.esFinLinea) todoMenosFuente)
  
 esSeparador,esFinLinea :: Char -> Bool esSeparador,esFinLinea :: Char -> Bool
-esSeparador x = x=='|' +esSeparador x = elem x "| " 
-esFinLinea  x = x=='\n'+esFinLinea  x = elem x "\n\r"
 </code> </code>
  
Línea 256: Línea 235:
 Vamos a desarrollar diferentes funciones para obtener información de esta lista.  Vamos a desarrollar diferentes funciones para obtener información de esta lista. 
  
-  * Antes que nada necesitamos definir un par de funciones auxiliares:+  * 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.     * //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 ''++''.     * //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''. \\ +  * 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//. +  * ¿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. 
-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 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 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//. 
-  - ?Cómo podemos saber cuántas páginas web distintas apuntan a una determinada página? //cuantasApuntan :: Eq b => b -> [(a,b)] -> Int//.+
  
-FIXME : 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. 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)] 
introalg/taller07_5.1180369151.txt.gz · Última modificación: 2018/08/10 03:03 (editor externo)