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 23:26] – nicolaswintroalg:taller07_5 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
Línea 106: Línea 106:
   and        = foldr (&&) True   and        = foldr (&&) True
   or         = foldr (||) False   or         = foldr (||) False
 +
 +
  
  
 ==== Ejercicios ==== ==== 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//").+  * 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 128: 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 145: Línea 152:
   encuentraEstafador [] _      = []   encuentraEstafador [] _      = []
   encuentraEstafador (x:xs) ys | existe (==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
  
 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. 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====
  
   * Definir //iguales :: Eq a => [a] -> [a] -> Bool// que decide si dos listas son iguales.   * 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.+  * 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'//.   * 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: 
-FIXME +<code> 
-Yo sacaría todo esto o lo reduciría a ser el último ejercicio de esta sección. +listadoSubsidio :: [(Int,String,Int)] 
- +listadoSubsidio = [(23763956,"Pedrito Rico",7), (36518184,"Daniel Socolof",2), (37643221,"Amaranta Buendía",1)] 
-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: +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")] 
-FIXME +</code>
-Pondría [(dni,Nombre)] y [(nombre,dni)] para poder usar fst y snd. +
-la:: yo quería dejar la cosa en esa forma para que ellos definieran su fst y snd para triplas, pero si quieres lo dejamos así. +
-Les daría un caso concreto definiendo dos constantes listadoSubsidio y listadoMunicipales para que prueben  +
-la:: eso quiere decir que les armemos los archivos de entrada nosotros, como para el caso de webGraph? +
-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' . +
-la:: pero tiene mucho más parecido con un problema real, no? vamos, por eso lo puse, pero lo podemos sacar, ningún problema. +
- +
-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. +
  
  
Línea 206: 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 214: 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 222: 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 243: Línea 228:
   Main> take 32 (map fst webGraph)   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/"   ["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/"
- 
  
  
Línea 251: 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//. Utilizar esto junto a //primeros//, //segundos// y //concatenaPares// para lograr el objetivo.   * ¿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 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.
Línea 260: Línea 245:
   * ¿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 
-la:: reescribir cómo? con ejemplos? 
  
 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.
introalg/taller07_5.1180394778.txt.gz · Última modificación: 2018/08/10 03:03 (editor externo)