Clase 3

• Revisar algunas soluciones de la Wiki.
• Funciones que toman funciones.
• Casos mas complejos de recursiones con listas.
• Resolución de ejercicios.
• Anuncios varios.

Veamos algunas soluciones presentadas 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 ( dividir y conquistar).

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 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.

• (P8,E19) Usando paraTodo, desdeHasta y noMultiplo, defina la función primo. Pruebe con los siguientes primos: 7, 73, 739, 7393, 73939, 739391, 7393913, 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).

• La proxima clase (martes 23 de Mayo) habrá practica supervisada de taller.
• Vamos a evaluar el taller, como un parcialito más.