Ciencias de la Computación FAMAF

Herramientas de usuario

Herramientas del sitio

Traza:
introalg:taller3

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:taller3 [2006/05/16 00:06] – nicolaswintroalg:taller3 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
Línea 2: Línea 2:
  
 ===== Plan para hoy ===== ===== Plan para hoy =====
 +  * Revisar algunas soluciones de la Wiki.
 +  * Funciones que toman funciones.
 +  * Casos mas complejos de recursiones con listas.
 +  * Resolución de ejercicios.
 +  * Anuncios varios.
  
 ===== Algunas soluciones de la clase anterior ====== ===== Algunas soluciones de la clase anterior ======
  
 Veamos algunas soluciones presentadas [[introalg:rincon | Wiki de Scripts Haskell]]. Veamos algunas soluciones presentadas [[introalg:rincon | Wiki de Scripts Haskell]].
 +
 +
 +  * Función ''cabeza'', duplicación de casos.
 +  * ¿Lista capicúa recursiva?
 +    * Calificadores de **clase** (''Eq a =>'')
 +    * Pattern matching es más general de lo que vimos.
 +  * La lista binaria ''listbin'' muy complicada
 +    * Todos los programas se puede hacer en un par de lineas y si no usamos definiciones locales y/o otras funciones que //dividan el problema en partes// ([[http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm | dividir y conquistar]]).
 +  
  
 ===== Clase ===== ===== Clase =====
Línea 11: Línea 25:
 Veamos el ejercicio 18 Veamos el ejercicio 18
  
-Defina la funci\'on //paraTodo: (A-> Bool)-> [A]-> Bool//, donde //paraTodo.p.xs// decide si todos los elementos de la lista //xs// cumplen con el **predicado** //p//.+----- 
 +Defina la función //paraTodo: (A-> Bool)-> [A]-> Bool//, donde //paraTodo.p.xs// decide si todos los elementos de la lista //xs// cumplen con el **predicado** //p//. 
 +-----
  
 Nuevamente esta función es el típico caso que se resuelve con un caso base y un caso inductivo Nuevamente esta función es el típico caso que se resuelve con un caso base y un caso inductivo
Línea 24: Línea 40:
   *Funciones de //alto orden//.   *Funciones de //alto orden//.
  
-Esto es muy poderoso porque permite escribir programas funcionales que toman programas funcionales y generan otros programas funcionales.+Esto es muy poderoso porque permite escribir programas funcionales que toman programas funcionales y generan otros programas funcionales. \\
 Las funciones son //ciudadanos de primera categoría// no como en otros lenguajes de programación (imperativos). Las funciones son //ciudadanos de primera categoría// no como en otros lenguajes de programación (imperativos).
  
Línea 50: Línea 66:
   noMultiplo 21 2 :: Bool   noMultiplo 21 2 :: Bool
  
-Con estos elementos y la función ''desdeHasta'' que ya figura en sus ''practico8.hs'', podemos construir la función ''primo'' (ejercicio)+Con estos elementos y la función ''desdeHasta'' que ya figura en sus ''practico8.hs'', podemos construir la función ''primo'' (ejercicio). 
 + 
 +También podemos usar aplicación parcial en los operadores (''+'', ''=='', ''*'') usando **secciones de los operadores**.  \\ 
 +Por ejemplo ver que todos los elementos de una lista son 0 lo escribimos como 
 + 
 +  Main> paraTodo (==0) [0,0,0,0,0] 
 +  True 
 +  Main> paraTodo (==0) (desdeHasta 0 20) 
 +  False 
 +  Main> :t (==0) 
 +  flip (==) 0 :: Num a => a -> Bool 
 + 
 +\\ 
 + 
 +Veamos ahora una función que "cierra" dos listas en una sola conteniendo pares. \\ 
 +Por ejemplo: 
 + 
 +  Main> cierra ["Saturnino", "Tamburrini", "Berlin"] [9,8,3] 
 +  [("Saturnino",9),("Tamburrini",8),("Berlin",3)] 
 +  
 +Esta función requiere inducción en dos listas al mismo tiempo, por lo tanto tenemos el //pattern matching// tendrá ahora **4 casos**. 
 + 
 +  * Caso(s) base(s) 
 +  * Caso(s) inductivo(s) 
 + 
 +  cierra :: [a] -> [a] -> [(a,a)] 
 +  cierra [] [] = [] 
 +  cierra (x:xs) [] = [] 
 +  cierra [] (y:ys) = [] 
 +  cierra (x:xs) (y:ys) = (x,y) : cierra xs ys 
 + 
 +Entonces probemos: 
 + 
 +  Main> cierra ["Saturnino", "Tamburrini", "Berlin"] [9,8,3] 
 +  ERROR - Cannot infer instance 
 +  *** Instance   : Num [Char] 
 +  *** Expression : cierra ["Saturnino","Tamburrini","Berlin"] [9,8,3] 
 + 
 +¿Cuál es el problema? \\ 
 +Tenemos un problema de tipos, el tipo de la función //no es lo suficientemente general//. \\ 
 +Lo corregimos para que sea ''cierra :: [a] -> [b] -> [(a,b)]''. 
 + 
 +Usando las ideas de este ejemplo podemos resolver los ejercicios 21 y 22 del práctico 8. 
 + 
 +\\ 
 + 
 +Generalicemos las funciones ''duplicar'' y ''multiplicar'' que vimos anteriormente. 
 + 
 +  duplicar :: [Int] -> [Int] 
 +  duplicar [] = [] 
 +  duplicar (x:xs) = x*2 : duplicar xs 
 + 
 +  multiplicar :: [Int] -> Int -> [Int] 
 +  multiplicar [] a = [] 
 +  multiplicar (x:xs) a = x*a : multiplicar xs a 
 + 
 +La estructura es la misma, estamos aplicando una función a cada elemento de la lista.\\ 
 +El ejercicio 24 dice: 
 + 
 +----- 
 +a) Defina la función //mapear:(A -> B) -> [A] -> [B]// que dadas una función //f// y una lista //xs//, aplica //f// a cada elemento de la lista.\\ 
 +Ejemplo: //mapear.primo.[1,2,3,4,5,6]=[false,true,true,false,true,false]//. 
 +----- 
 + 
 +Tenemos nuevamente una **función de alto orden** y su definición es bien sencilla, con los dos casos (vacía y al menos un elemento) alcanza. 
 + 
 +  mapear :: (a->b) -> [a] -> [b] 
 +  mapear f [] = [] 
 +  mapear f (x:xs) = f x : mapear f xs 
 + 
 +Ahora ''duplicar'' es un caso particular si usamos //la sección del operador ''*''//. 
 + 
 +  Main> mapear (*2) [1,2,3] 
 +  [2,4,6] 
 + 
 +Podemos definir ''duplica' '' sin tener que hablar de la lista! 
 + 
 +  duplica' = mapear (*2) 
 + 
 +Vemos como funciona haciendo los pasos de reducción de ''duplica' [1,2]''. \\ 
 + 
 +  * Gracias a la //currificación// tenemos funciones que no necesitan nombrar todos sus argumentos. 
 +  * Notación muy compacta y legible.
  
 ===== Ejercicios ===== ===== Ejercicios =====
-  * (P8,E19) Usando ''paraTodo'', ''desdeHasta'' y ''noMultiplo'', defina la función ''primo''. // +  * (P8,E19) Usando ''paraTodo'', ''desdeHasta'' y ''noMultiplo'', defina la función ''primo''. Pruebe con los siguientes primos: 7, 73, 739, 7393, 73939, 739391, 7393913, [[http://en.wikipedia.org/wiki/Prime_number#Trivia|73939133]], donde sus sucesores no lo son.
-Pruebe con los siguientes primos: 7, 73, 739, 7393, 73939, 739391, 7393913, [[http://en.wikipedia.org/wiki/Prime_number|73939133]], donde sus sucesores no lo son. +
-  +
   * (P8,E21) Defina la función ''iguales :: Eq a => [a] -> [a] -> Bool'' que retorna //true// si las listas son iguales.   * (P8,E21) Defina la función ''iguales :: Eq a => [a] -> [a] -> Bool'' que retorna //true// si las listas son iguales.
-  * (P8,E24) Definla la función ''mapear :: (a->b) -> [a] -> [b]'', que dada una función ''f'' y una lista ''xs'' aplica ''f'' a cada elemento de la lista. Escriba ''duplicar' '' y ''multiplicar' '' utilizando ''mapear''.+  * (P8,E24) Defina la función ''multiplicar' '' usando ''mapear''. Intente escribirla sin usar el argumento que nombra la lista. 
 +  * (P8,E24) Defina la la función ''filtrar :: (a->Bool) -> [a] -> [a]'', que dado un predicado ''p'' y una lista ''xs'' , devuelve todos los elementos que satisfacen ''p''. Ejemplo ''filtro primo (desdeHasta 1 100)'' devuelve todos los primos entre 1 y 100 (casi el ejercicio 20). 
 + 
 +===== Anuncios ===== 
 + 
 +  * La proxima clase (martes 23 de Mayo) habrá practica supervisada de taller. 
 +  * Vamos a evaluar el taller, como un parcialito más.
introalg/taller3.1147737963.txt.gz · Última modificación: 2018/08/10 03:03 (editor externo)