Diferencias

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

--- introalg:taller3 [2006/05/16 14:03] – nicolasw
+++ introalg:taller3 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
@@ Línea 1: / Línea 1: @@
+====== Clase 3 ======
+===== 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 ======
+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 =====
+Veamos el ejercicio 18
+-----
+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
+  paraTodo :: (a->Bool) -> [a] -> Bool
+  paraTodo p [] = True
+  paraTodo p (x:xs) = p x && paraTodo p xs
+Notemos que esta función toma como parámetro **una función**.
+  *Funciones que toman funciones.
+  *Funciones de //alto orden//.
+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).
+Definimos rápidamente el predicado ''noMultiplo p n'' que indica cuando ''p'' no es múltiplo de ''n''.
+  noMultiplo :: Int -> Int -> Bool
+  noMultiplo p n = p `mod` n >0
+Notamos:
+  * Volvimos //infija// la función ''mod''.
+  * Usamos una versión [[http://en.wikipedia.org/wiki/Currying|currificada]].
+Podríamos haber escrito
+  noMultiplo' :: (Int,Int) -> Bool
+  noMultiplo' (p,n) = p `mod` n >0
+Sin embargo son diferentes pues ''noMultiplo'' permite la **aplicación parcial**
+  Main> :t noMultiplo
+  noMultiplo :: Int -> Int -> Bool
+  Main> :t noMultiplo 20
+  noMultiplo 21 :: Int -> Bool
+  Main> :t noMultiplo 21 2
+  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).
+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 =====
+  * (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.
+  * (P8,E21) Defina la función ''iguales :: Eq a => [a] -> [a] -> Bool'' que retorna //true// si las listas son iguales.
+  * (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.