Diferencias

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

--- introalg:taller09_6 [2009/05/04 13:05] – laura
+++ introalg:taller09_6 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
@@ Línea 48: / Línea 48: @@
 Las listas son una estructura que por definición contiene un número arbitrario de elementos, por lo tanto son el contexto natural para aplicar funciones recursivas. Hemos distinguido tres grandes tipos de funciones recursivas en listas:
   * **aplicaciones**: toman una lista y devuelven otra lista que es el resultado de aplicar una función a todos los elementos de la lista original. Su signatura de tipos suele seguir el esquema
   aplica :: [a] -> [b]
 donde el tipo de la lista inicial no necesariamente tiene que ser el mismo que el de la lista resultante, ya que la función que aplicamos a cada elemento puede cambiar ese tipo (por ejemplo, si cambiamos de booleano a 0 o 1).
   * **filtros**: toman una lista y devuelven solamente los elementos de esa lista que cumplen con un determinado predicado. Su signatura de tipos suele seguir el esquema
   filtra :: [a] -> [a]
 donde el tipo de la lista inicial tiene que ser exactamente el mismo que el de la lista resultante, ya que devolvemos elementos del mismo tipo solamente que podemos devolver menos elementos, descartando los que no cumplen el predicado (por ejemplo, los que no son pares).
   * **acumuladores**: toman cada uno de los elementos de una lista y hacen alguna operación para acumular ese elemento con el resultado de hacer lo mismo con el resto de la lista. Su signatura de tipos suele seguir el esquema
   acumula :: [a] -> b
 fíjense que el tipo del resultado es distinto que el de la lista inicial, de hecho, ni siquiera es necesario que sea una lista. El tipo del resultado es exactamente **el neutro de la operación** que estemos aplicando para acumular el resultado (por ejemplo, en una sumatoria es el 0, en una productoria el 1, etc.).
@@ Línea 77: / Línea 83: @@
 <code>
-cuadrado :: Int -> Int
-cuadrado x = x^2
 cuadrados :: [Int] -> [Int]
 cuadrados []     = []
 cuadrados (x:xs) = cuadrado x : cuadrados xs
-</code>
-<code>
+cuadrado :: Int -> Int
-rangoEdades :: [Int] -> [String]
+cuadrado x = x^2
-rangoEdades []     = []
-rangoEdades (x:xs) = rangoEdad x : rangoEdades xs
 </code>
@@ Línea 98: / Línea 98: @@
-Ahora que sabemos esto, resolvamos la función ''multiplicar :: Int -> [Int] -> [Int]'' que dada un número //n// y una lista, multiplica cada uno de los elementos por //n//. Ejemplo: //multiplicar.3.[3,0,-2] = [9,0,-6]//.
+Ahora que sabemos esto, resolvamos la función ''multiplicar :: Int -> [Int] -> [Int]'' que dada un número //n// y una lista, multiplica cada uno de los elementos por //n//. Ejemplo: ''multiplicar 3 [3,0,-2] = [9,0,-6]''.
@@ Línea 108: / Línea 108: @@
 <code>
-esPar :: Int -> Bool
+soloTrue :: [Bool] -> [Bool]
-esPar = esDivisor 2
+soloTrue [] = []
+soloTrue (x:xs) | x == True = x : soloTrue xs
+                | otherwise =     soloTrue xs
+</code>
+<code>
 soloPares :: [Int] -> [Int]
 soloPares [] = []
 soloPares (x:xs) | esPar x   =  x : soloPares xs
                  | otherwise =      soloPares xs
+esPar :: Int -> Bool
+esPar x = mod x 2 == 0
 </code>
 <code>
-primeraEsM :: [Char] -> Bool
-primeraEsM xs = cabeza xs == 'm'
 empiezaM :: [String] -> [String]
 empiezaM [] = []
 empiezaM (x:xs) | primeraEsM x = x : empiezaM xs
                 | otherwise    =     empiezaM xs
+primeraEsM :: [Char] -> Bool
+primeraEsM xs = head xs == 'm'
 </code>
@@ Línea 134: / Línea 141: @@
                     | otherwise =      _____________ xs
-Ahora que sabemos esto, resolvamos la función ''soloPares :: [Int] -> [Int]'' que dada una lista de enteros devuelve una lista que contiene sólo los pares de la lista original. Ejemplo: //soloPares [6,5,12,21] = [6,12]//.
+Ahora que sabemos esto, resolvamos la función ''soloMultiplos3 :: [Int] -> [Int]'' que dada una lista de enteros devuelve una lista que contiene sólo los múltiplos de 3 de la lista original. Ejemplo: //soloMultiplos3 [6,5,12,21,22] = [6,12,21]//.
 ==== Acumuladores (foldr) ====
@@ Línea 149: / Línea 156: @@
 <code>
-producto :: Int -> Int -> Int
-producto x y = x*y
 productoria :: [Int] -> Int
 productoria []     = 1
 productoria (x:xs) = producto x (productoria xs)
+producto :: Int -> Int -> Int
+producto x y = x*y
 </code>
@@ Línea 176: / Línea 183: @@
-Como el resultado de la función no es una lista, el resultado del caso base no es una lista vacía. El resultado del caso base debe ser definido para cada función, ya que debe ser el neutro del operador que se utilice en la función. Por lo tanto, en los acumuladores tendremos un argumento más que en las aplicaciones y los filtros, justamente, el neutro.
+Como el resultado de la función no es una lista, el resultado del caso base no es una lista vacía. El resultado del caso base debe ser definido para cada función, ya que debe ser el **neutro del operador** que se utilice en la función.
-Ahora que sabemos esto, resolvamos la función ''longitud :: [Int] -> Int'' que dada una lista de enteros computa su largo. Ejemplo: //longitud.[3,0,-2] = 3//.
+Ahora que sabemos esto, resolvamos la función ''longitud :: [Int] -> Int'' que dada una lista de enteros computa su largo. Ejemplo: //longitud [3,0,-2] = 3//.
-Otro ejemplo: la función ''sumaPares :: [(Int, Int)] -> Int'', que dada una lista de pares de números, devuelve la sumatoria de todos los números de todos los pares. Ejemplo: //sumaPares.[(1,2)(7,8)(11,0)] = 29//.
+Otro ejemplo: la función ''sumaPares :: [(Int, Int)] -> Int'', que dada una lista de pares de números, devuelve la sumatoria de todos los números de todos los pares. Ejemplo: //sumaPares [(1,2)(7,8)(11,0)] = 29//.
 Más ejercicios: la función ''existe :: a -> [a] -> Bool'', que dado un elemento y una lista, devuelve True si el elemento está en la lista. Fíjense que se trata de una generalización del ejercicio anterior.
@@ Línea 191: / Línea 198: @@
 Muchas funciones necesitan hacer cosas complejas, y para eso combinan dos o más de los tipos de funciones recursivas en listas que hemos visto. Veamos los siguientes ejemplos:
-  * La función ''sumaPares :: [Int] -> Int'', que suma sólo los elementos pares de una lista.
+La función ''sumaPares :: [Int] -> Int'', que suma sólo los elementos pares de una lista. Esta función es una combinación de un filtro (nos quedamos solamente con los pares) y un acumulador (sumamos esos elementos con los que nos hemos quedado).
-  * La función ''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.
+<code>
-  * La función ''edadPromedio:: [(String,Int)] -> Int'', que dada una lista de pares //(nombre,edad)//, retorna el promedio de edad de las personas.
+sumaPares :: [Int] -> Int
+sumaPares [] = 0
+sumaPares (x:xs) | mod x 2 == 0 = x + sumaPares xs
+                 | otherwise    =     sumaPares xs
+</code>
+Fíjense que el resultado es el resultado propio de un acumulador, es decir, no es una lista, por lo tanto para el caso base tenemos que usar el neutro de la operación, en este caso, como la operación es la suma, el resultado para el caso base es el 0.
+También podríamos definir la función de forma que queden más separados el filtro y el acumulador, definiendo las funciones por separado y usándolas luego combinadas, primero aplicando el filtro y luego sumando los elementos que quedaron seleccionados en el filtro. Para indicar que primero se tiene que aplicar una operación y después la otra, usamos paréntesis:
+<code>
+sumaPares' :: [Int] -> Int
+sumaPares' xs = suma (pares xs)
+pares :: [Int] -> [Int]
+pares [] = []
+pares (x:xs) | mod x 2 == 0 = x : pares xs
+             | otherwise    =     pares xs
+suma :: [Int] -> Int
+suma [] = 0
+suma (x:xs) = x + suma xs
+</code>
+Fíjense que ahora no tenemos que definir caso base y caso recursivo para definir ''sumaPares'', porque ya están definidos en las funciones ''sumatoria'' y ''soloPares''.
+Pero no les resultan muy familiares estas funciones ''pares'' y ''suma''? Efectivamente, son nuestras viejas amigas ''soloPares'' y ''sumatoria'', así que podríamos directamente usar ésas para definir ''sumaPares'', de la siguiente forma:
+<code>
+sumaPares'' :: [Int] -> Int
+sumaPares'' xs = sumatoria (soloPares xs)
+</code>
+Corto, fácil de leer y reusando código! Qué más queremos! ;-)
+Veamos otros ejemplos: la función ''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. En este caso estamos combinando una aplicación (calcular el 5% y sumarlo) y un acumulador (sumar todos los elementos de la lista a la que se ha aplicado el acumulador). También en este caso podemos definir primero las funciones por separado: la aplicación (calcular y sumar 5%) y el acumulador (sumatoria), y aplicarlos combinadamente, primero la aplicación y después la sumatoria.
+Cómo calculamos la función ''edadPromedio:: [(String,Int)] -> Int'', que dada una lista de pares //(nombre,edad)//, retorna el promedio de edad de las personas? En este caso tenemos un acumulador (el promedio), y vamos a necesitar algo más...
 ===== Recursión en dos argumentos =====
@@ Línea 232: / Línea 271: @@
 ====== Ejercicios ======
+==== Repaso de prolog ====
+  * A partir de la siguiente base de conocimiento en prolog, crear las reglas necesarias para que el intérprete nos diga si una persona alérgica a la frutilla puede comer helado de frutilla:
+<code>
+esAlérgico(pepe,kiwi).
+esAlérgico(juan,frutilla).
+esAlérgico(maría,melocotón).
+tiene(helado,Y) :- helado(Y).
+tiene(torta,Y) :- torta(Y).
+</code>
+==== Repaso de haskell ====
   * Definir la función **estanOrdenados**, //estanOrdenados :: (Int,Int) -> Bool//, que dado un par de números enteros devuelve True si los números están ordenados de menor a mayor.
@@ Línea 242: / Línea 295: @@
   * Definir la función **restaPositiva**, //restaPositiva:: (Int,Int) -> Int//, que dado un par de enteros, devuelve el valor de la resta del mayor menos el menor.
+  * Definir la función **esSigno**, //esSigno :: String -> (String,String,String) -> Bool//, que dado un string //s// que representa un signo zodiacal, una tresupla //(n,t,z)// que representa el nombre, el trabajo y el signo zodiacal de una persona, devuelve True si la persona es del signo //s// y False si es de cualquier otro signo.
+  Ejemplo: esSigno ``aries'' (``Ana'',''recepcionista'',''aries'') = True.
+  Ejemplo: esSigno ``leo'' (``Mario'',''tornero'',''libra'') = False.
+  * Definir la función **cuatroCabezas**, //cuatroCabezas :: [ [ a ] ] -> (a,a,a,a)//, que dada una lista de listas de cualquier tipo devuelve una cuatrupla con los primeros elementos de las cuatro primeras listas de la lista original.
+  Ayuda: se puede usar la función "head" definida en el preámbulo, o definir la función "cabeza".
+==== Funciones recursivas ====
   * Definir la función **librosRecomendados**, //librosRecomendados :: [(String,Bool)] -> [String]//, que dada una lista de pares //(nombre,esRecomendado)//, devuelve una lista con sólo los nombres de los libros recomendados.
@@ Línea 247: / Línea 309: @@
   * Definir la función **peliculasAccion**, //peliculasAccion :: [(String,Bool)] -> [String]//, que dada una lista de pares //(nombre,esAccion)//, devuelve una lista con solo los nombres de las películas de acción.
-  Ejemplo: peliculasAccion [(``Rambo'',True),(``E.T.'',False),(``Duro de Matar'',True)] = [``Rambo'',``Duro de Matar''].
+  Ejemplo: peliculasAccion [("Rambo",True),("E.T.",False),("Duro de Matar",True)] = ["Rambo","Duro de Matar"].
-  * Definir la función **esSigno**, //esSigno :: String -> (String,String,String) -> Bool//, que dado un string //s// que representa un signo zodiacal, una tresupla //(n,t,z)// que representa el nombre, el trabajo y el signo zodiacal de una persona, devuelve True si la persona es del signo //s// y False si es de cualquier otro signo.
-  Ejemplo: esSigno ``aries'' (``Ana'',''recepcionista'',''aries'') = True.
-  Ejemplo: esSigno ``leo'' (``Mario'',''tornero'',''libra'') = False.
   * Definir la función **cuadrados**, //cuadrados :: [Int] -> [Int]//, que dada una lista de enteros //xs// devuelve una lista con el cuadrado de cada uno de los miembros de //xs//.
@@ Línea 270: / Línea 328: @@
   * Definir la función **cuantos0**, //cuantos0 :: [Int] -> Int//, que dada una lista de enteros devuelve un entero con la cantidad de n˙meros 0 que hay en la lista original.
   Ayuda: recordar cómo se hizo la función "longitud".
-  * Definir la función **cuatroCabezas**, //cuatroCabezas :: [ [ a ] ] -> (a,a,a,a)//, que dada una lista de listas de cualquier tipo devuelve una cuatrupla con los primeros elementos de las cuatro primeras listas de la lista original.
-  Ayuda: se puede usar la función "head" definida en el preámbulo, o definir la función "cabeza".
   * Definir la función **cuantosEntre**, //cuantosEntre :: Int -> Int -> [Int] -> Int//, que dados dos números //n// y //m// y una lista de enteros //xs//, devuelve la cantidad de números de //xs// que están entre //n// y //m//.
@@ Línea 284: / Línea 339: @@
   * 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.
@@ Línea 291: / Línea 344: @@
   * 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>