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:48] – nicolaswintroalg:taller07_5 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
Línea 114: Línea 114:
   * 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//.   * 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.   * ¿Cuáles son el //paraTodo// y //existe// del preámbulo estandar? Revisar su definición.
 +
 +
  
  
Línea 150: 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:   * 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:
Línea 166: Línea 169:
 listadoMuni = [("Rubén Daniele",7632663,"21/12/1957"),("Amanda Buendía",37643221,"04/06/1987"),("Caridad Canelón",41122332,"29/2/2000")] listadoMuni = [("Rubén Daniele",7632663,"21/12/1957"),("Amanda Buendía",37643221,"04/06/1987"),("Caridad Canelón",41122332,"29/2/2000")]
 </code> </code>
 +
  
 ===== Manejando cosas más complejas ===== ===== Manejando cosas más complejas =====
Línea 187: 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 195: 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 203: 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 224: 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 232: 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 241: 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.1180396110.txt.gz · Última modificación: 2018/08/10 03:03 (editor externo)