Ciencias de la Computación FAMAF

Herramientas de usuario

Herramientas del sitio

Traza:
introalg:taller07_4

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_4 [2007/05/14 17:43] – nicolaswintroalg:taller07_4 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
Línea 1: Línea 1:
 ====== Clase 4 ====== ====== Clase 4 ======
 +
 +
  
  
Línea 5: Línea 7:
 ===== Aplicación parcial (secciones) ===== ===== Aplicación parcial (secciones) =====
  
-Tomemos la siguente función Haskell que es una ligera variación de la que se encuentra en el problemario //esMultiplo//.+Tomemos la siguente función Haskell que es una ligera variación de //esMultiplo// que está en el problemario.
  
 <code> <code>
Línea 17: Línea 19:
  
 Esto lo podemos leer como que //esDivisor// es una función que toma un entero y **devuelve una función** de tipo //Int->Bool//. Esto lo podemos leer como que //esDivisor// es una función que toma un entero y **devuelve una función** de tipo //Int->Bool//.
-Esto es lo mismo que pasa en los ejercicios 5f, 5g y 5i del Práctico 5. +Esto es lo mismo que pasa en los ejercicios 5f, 5g y 5i del Práctico 5, y muestra que una función es un ciudadano de primera categoría en Haskell, puede ser devuelto como resultado de una función y también veremos que puede ser un parámetro de entrada. 
-De hecho le podemos preguntar a Hugs por el tipo de+ 
 +Para ganar confianza podemos preguntar a Hugs por el tipo de la aplicación parcial.
  
   Main> :t esDivisor 2   Main> :t esDivisor 2
Línea 28: Línea 31:
 <code> <code>
 esPar :: Int -> Bool esPar :: Int -> Bool
-esPar = esDivisor 2+esPar x = esDivisor 2 x
 </code> </code>
  
 La función devuelve //True// si y solo si el entero es divisible por 2! La función devuelve //True// si y solo si el entero es divisible por 2!
-Notamos que esta definición es idéntica a esta versión **con argumentos**.+Notamos que esta definición es idéntica a esta versión **sin argumentos** que utiliza el mecanismo de secciones
 <code> <code>
 esPar' :: Int -> Bool esPar' :: Int -> Bool
-esPar' x = esDivisor 2 x+esPar' = esDivisor 2
 </code> </code>
  
-Esta forma de denotar funciones se denomina [[http://en.wikipedia.org/wiki/Currying|currificación]], en honor al lógico [[http://es.wikipedia.org/wiki/Haskell_Curry|Haskell Curry]] ((Si si, el lenguaje Haskell se llama así por Haskell Curry.)).+Esta forma de escribir funciones se denomina [[http://en.wikipedia.org/wiki/Currying|currificación]], en honor al lógico [[http://es.wikipedia.org/wiki/Haskell_Curry|Haskell Curry]] ((Si si, el lenguaje Haskell se llama así por Haskell Curry.)).
  
 Este mecanismo de aplicación parcial de argumentos resulta muy elegante para escribir funciones. Este mecanismo de aplicación parcial de argumentos resulta muy elegante para escribir funciones.
Línea 59: Línea 62:
   [True,False,True,False]   [True,False,True,False]
  
-Le tiene que quedar claro que esta es una forma **elegante** y **compacta** de definir nuevas funciones a partir de otras, pero no es imprescindible. Por ejemplo, para el tercer ejemplo podemos definir la función auxiliar+Tiene que quedar claro que esta es una forma **elegante** y **compacta** de definir nuevas funciones a partir de otras, pero no es imprescindible. Por ejemplo, para el tercer ejemplo podemos definir la función auxiliar
  
 <code> <code>
Línea 71: Línea 74:
   [False,False,False,False]   [False,False,False,False]
  
 +=== Ejercicio ===
 +
 +  * Utilizando aplicación parcial en //( /= )//, definir la función //noEsCero :: Int -> Bool// que decide si un entero //x// es distinto a 0.
  
 ===== Generalización de las funciones vistas (map, filter, fold) ===== ===== Generalización de las funciones vistas (map, filter, fold) =====
 +
 +
 +
 +
  
  
Línea 85: Línea 95:
  
 ?No estamos ya cansados de escribir siempre lo mismo? ?No estamos ya cansados de escribir siempre lo mismo?
-Veamos solo algunas de las funciones de //tipo aplicación//, son todas idénticas, salvo por la **operación o función** que se aplica a cada elemento.+Las funciones de //tipo aplicación//, son todas idénticas, salvo por la **operación o función** que se aplica a cada elemento.
  
 <code> <code>
Línea 94: Línea 104:
  
 <code> <code>
-veintePorCiento : [Float] -> [Float] +veintePorCiento :: [Float] -> [Float] 
 veintePorCiento []     = [] veintePorCiento []     = []
 veintePorCiento (x:xs) = 0.2*x : veintePorCiento xs veintePorCiento (x:xs) = 0.2*x : veintePorCiento xs
Línea 116: Línea 126:
 Entonces **generalizemos** definiendo una función que toma como primer argumento la función que se aplicará a cada elemento de la lista. Entonces **generalizemos** definiendo una función que toma como primer argumento la función que se aplicará a cada elemento de la lista.
  
-\\ +Vemos nuevamente la aplicación del **alto orden**, un nombre muy pomposo para algo bastante natural: **las funciones son un tipo más que puede ser tomado como parámetro y devuelto como resultado**.
-\\ +
-------+
  
-  * Definir la función //mapNumero.f.xs//, //mapNumero : (Int -> Int) -> [Int] -> [Int]// que dada una función //f// y una lista de enteros //xs//, les aplica una función aritmética //f// y concatena el resultado en una lista. Ejemplo: //mapNumero.(+2).[0,1,2,3] = [2,3,4,5]//.+De nuevo, se dice que en Haskell las funciones son //ciudadanos de primera categoría//. 
 +Esto no ocurre en la mayoría de los //lenguajes imperativos// como C, C++, Pascal, Basic, etc. .
  
-  probar con mapNumeros.(*2).[0,1,2,3], mapNumeros.absoluto.[-10,0,10].+Notar que ya vimos funciones que devuelven funciones! Por ejemplo.
  
------- +  esDivisor :: Int -> (Int -> Bool) 
-\\ +  esDivisor 2 :: Int -> Bool
-\\+
  
-Esta función es la primera que creamos que utiliza **alto orden**, un nombre muy pomposo para algo bastante natural: **las funciones son un tipo más que puede ser tomado como parámetro y devuelto como resultado**. 
  
-Se dice que en Haskell las funciones son //ciudadanos de primera categoría//. +=== Ejercicio ===
-Esto no ocurre en la mayoría de los //lenguajes imperativos// como C, C++, Pascal, Basic, etc. .+
  
-Notar que ya vimos funciones que devuelven funciones!+  * Definir la función //mapNumeros.f.xs//, //mapNumeros : (Int -> Int) -> [Int] -> [Int]// que dada una función //f// y una lista de enteros //xs//, les aplica una función aritmética //f// y concatena el resultado en una lista. Ejemplo: //mapNumeros.(+2).[0,1,2,3] = [2,3,4,5]//. 
 + 
 +  probar con mapNumeros.(*2).[0,1,2,3], mapNumeros.absoluto.[-10,0,10].
  
-  esDivisor :: Int -> (Int -> Bool) 
  
-es un ejemplo. 
  
  
Línea 145: Línea 151:
  
 <code> <code>
-esPar :: Int -> Bol +esPar :: Int -> Bool 
-esPar x = x `mod` 2 == 0+esPar = esDivisor 2
  
 soloPares :: [Int] -> [Int] soloPares :: [Int] -> [Int]
Línea 165: Línea 171:
  
 Entonces plantemos el mismo tipo de ejercicio, una generalización que tome como primer parámetro un **predicado**, es decir una función que devuelve un booleano, que decidirá si cada elemento se conserva o se filtra. Entonces plantemos el mismo tipo de ejercicio, una generalización que tome como primer parámetro un **predicado**, es decir una función que devuelve un booleano, que decidirá si cada elemento se conserva o se filtra.
 +
 +=== Ejercicio ===
  
   * Definir la función //filtraNumeros.p.xs//, //filtraNumeros : (Int -> Bool) -> [Int] -> [Int]// que dada un predicado //p// y una lista de enteros //xs// devuelve la lista que contiene sólo aquellos números de //xs// que devuelven //True// en la predicado //p//. Ejemplo: //filtraNumeros.entre0y9.[11,4,37,3,10] = [4,3]//. Un ejemplo con algunas implicaciones más: //filtraNumeros.(esDivisor.3).[1,2,3,4,5,6,7,8,9,10] = [3,6,9]//.   * Definir la función //filtraNumeros.p.xs//, //filtraNumeros : (Int -> Bool) -> [Int] -> [Int]// que dada un predicado //p// y una lista de enteros //xs// devuelve la lista que contiene sólo aquellos números de //xs// que devuelven //True// en la predicado //p//. Ejemplo: //filtraNumeros.entre0y9.[11,4,37,3,10] = [4,3]//. Un ejemplo con algunas implicaciones más: //filtraNumeros.(esDivisor.3).[1,2,3,4,5,6,7,8,9,10] = [3,6,9]//.
  
   probar con filtraNumeros.entre0y9.[], filtraNumeros.entre0y9.[10,20,30].   probar con filtraNumeros.entre0y9.[], filtraNumeros.entre0y9.[10,20,30].
 +
 +
 +
  
  
Línea 187: Línea 198:
  
 productoria :: [Int] -> Int productoria :: [Int] -> Int
-productoria []     = 0+productoria []     = 1
 productoria (x:xs) = producto x (productoria xs) productoria (x:xs) = producto x (productoria xs)
 </code> </code>
Línea 195: Línea 206:
 concatenaInt :: [[Int]] -> [Int] concatenaInt :: [[Int]] -> [Int]
 concatenaInt []       = [] concatenaInt []       = []
-concatenaInt (xs:xss) = xs ++ concatenaInt xss+concatenaInt (xs:xss) = (++) xs (concatenaInt xss)
 </code> </code>
  
-Hacer esta primera generalización.+=== Ejercicio === 
 + 
 +Definir la primera generalización.
  
   * Definir la función //paraTodoInt.p.xs//, //paraTodoInt : (Int->Bool) -> [Int] -> Bool//, que dado un predicado //p// retorna verdadero si y solo si, el predicado es válido para todos los elementos de la lista. Ejemplo //paraTodoInt.multiplo2.[2,4,6] = True//.   * Definir la función //paraTodoInt.p.xs//, //paraTodoInt : (Int->Bool) -> [Int] -> Bool//, que dado un predicado //p// retorna verdadero si y solo si, el predicado es válido para todos los elementos de la lista. Ejemplo //paraTodoInt.multiplo2.[2,4,6] = True//.
Línea 209: Línea 222:
  
   probar con acumulaInt.(+).0.[1,2,3], acumulaInt.(*).1.[1,2,3].   probar con acumulaInt.(+).0.[1,2,3], acumulaInt.(*).1.[1,2,3].
- 
  
 ===== Escribamos las versiones más generales ===== ===== Escribamos las versiones más generales =====
Línea 228: Línea 240:
  
 <code> <code>
-mapa : (a -> b) -> [a] -> [b]+mapa :: (a -> b) -> [a] -> [b]
 mapa f []     = mapa f []     =
 mapa f (x:xs) = mapa f (x:xs) =
Línea 250: Línea 262:
 filtro p (x:xs) = filtro p (x:xs) =
 </code> </code>
 +
 +
  
 ==== Acumuladores (fold) ==== ==== Acumuladores (fold) ====
Línea 263: Línea 277:
  
 Detectamos: Detectamos:
-  * Un "*cero*" respecto a la acumulación (//True// es neutro de la conjunción).+  * Un "**cero**" respecto a la acumulación (//True// es neutro de la conjunción).
   * Una función de acumulación que a partir del elemento actual y lo acumulado en la llamada recursiva sobre //xs//, obtiene el valor de lo acumulado en el total //x:xs//.   * Una función de acumulación que a partir del elemento actual y lo acumulado en la llamada recursiva sobre //xs//, obtiene el valor de lo acumulado en el total //x:xs//.
  
-Podemos reescribirla de la siguiente manera par que la función de acumulación sea más explícita.+Podemos reescribirla de la siguiente manera para que la función de acumulación sea más explícita.
  
 <code> <code>
-ceroUnoyAnteriores :: Int -> Bool -> Bool +ceroUnoYAnteriores :: Int -> Bool -> Bool 
-ceroUnoyAnteriores x b = (x==0 || x==1) && b+ceroUnoYAnteriores x b = (x==0 || x==1) && b
  
 todos0y1' :: [Int] -> Bool todos0y1' :: [Int] -> Bool
 todos0y1' []     = True todos0y1' []     = True
-todos0y1' (x:xs) = ceroUnoyAnteriores x (todos0y1' xs)+todos0y1' (x:xs) = ceroUnoYAnteriores x (todos0y1' xs)
 </code> </code>
  
Línea 292: Línea 306:
  
 ===== Reescribiendo funciones usando map, fold y filter ===== ===== Reescribiendo funciones usando map, fold y filter =====
 +
 +
 +
  
 ==== Ejercicios ==== ==== Ejercicios ====
  
   * Escribir //duplicar// y //multiplicar// con //mapa//.   * Escribir //duplicar// y //multiplicar// con //mapa//.
 +    * Reescribir ambas utilizando aplicación parcial sobre //mapa// para evitar escribir el argumento de la lista.
 +  * Utilizando //mapa// escribir la función //largos :: [String] -> [Int]// que dada una lista de cadenas, retorna la lista con la longitud de cada una.
   * Escribir //soloPares// y //quitar0s// con //filtro//.   * Escribir //soloPares// y //quitar0s// con //filtro//.
 +    * Reescribir ambas utilizando aplicación parcial sobre //mapa// para evitar escribir el argumento de la lista.
 +  * Escribir //concatenaInt// usando //acumula//.
 +  * Escribir //sumatoria// usando aplicación parcial con //acumula//.
   * Escribir //paraTodoInt// usando //acumula//.   * Escribir //paraTodoInt// usando //acumula//.
   * Escribir //longitud// usando //acumula//.   * Escribir //longitud// usando //acumula//.
   * Escribir //reversa// usando //acumula//.   * Escribir //reversa// usando //acumula//.
-  * **DIFÍCIL** Escribir //mapa// y //filtro// usando //acumula//.+  * **(DIFÍCIL)** Escribir //mapa// y //filtro// usando //acumula//.
introalg/taller07_4.1179164593.txt.gz · Última modificación: 2018/08/10 03:03 (editor externo)