informática (27)

Vista previa del material en texto

Programación Funcional con Haskell
Mauro Jaskelioff
22/03/2016
Hay dos maneras de construir un diseño de software:
Una manera es hacerlo de manera tan simple que sea
obvio que no hay deficiencias.
La otra es hacerlo de manera tan complicada que no
haya deficiencias obvias.
Tony Hoare, 1980
Desaf́ıos del Software
I Sistemas de software gigantes, cores múltiples, sistemas
distribuidos.
I Costo y tiempo de desarrollo.
I Confianza en los programas desarrollados
I ¿Qué tecnoloǵıa nos permitirá lidiar con los desaf́ıos?
La arquitectura de Von Neumann
I Una idea en los 1940’ que simplificó en forma práctica y
elegante varios problemas de ingenieŕıa y programación.
I Las condiciones han cambiado, pero, la máquina de Von
Neumann es, esencialmente, lo que ahora conocemos como
computadoras.
I En su forma más simple, consiste de un CPU, una memoria y
un tubito que los une.
I La tarea de los programas es modificar los contenidos de la
memoria en forma significativa.
I Todas las modificaciones se hacen a través del tubito!
Lenguajes de Von Neumann
I Los lenguajes imperativos fueron creados para programar esta
computadora.
I Son versiones complejas, de alto nivel, de la máquina de Von
Neumann
I ¡Se definen por su traducción a la máquina!
I La caracteŕıstica de estos lenguajes es:
I Las variables representan celdas de memoria.
I Los comandos de control representan saltos y comparaciones.
I La asignación imita la obtención y almacenamiento de datos.
I Separación entre datos y programas.
I Dada la popularidad de los lenguajes de Von Neumann, otras
arquitecturas no fueron desarrolladas.
Algunas problemas de los programas imperativos
I Mantienen un estado invisible.
I Uno debe ejecutar los programas mentalmente para
entenderlos.
I No son composicionales.
I Es dif́ıcil abstraer patrones comunes.
I Fuerzan un orden de ejecución.
I Semántica compleja (o directamente, dada por la
implementación).
I Ausencia de propiedades matemáticas útiles.
Ejemplo
Cálculo del producto escalar de dos vectores:
c := 0
for i := 1 step 1 until n do
c := c + a [ i ] ∗ b [ i ]
Comparemos con:
prod = sum ◦ zipWith (∗)
Requerimientos para un Lenguaje de Programación
Moderno
I Los programas deben poder ser escritos en forma clara,
concisa, y a un alto nivel de abstracción.
I Se debe poder desarrollar componentes de software generales,
reusables y modulares.
I La semántica debe ser clara para facilitar la verificación formal.
I Debe permitir el prototipado rápido y proveer herramientas
potentes.
I Debe facilitar la programación paralela.
I Debe tener propiedades matemáticas útiles.
Programación funcional
I La programación funcional cumple en buena medida con estos
requerimientos.
I No usa un modelo de computación basado en máquinas sino
en un lenguaje simple y elegante (el λ-cálculo).
I Su simpleza y versatilidad lo hacen ideal para aprender
conceptos de
I programación,
I lenguajes de programación,
I computabilidad,
I semántica,
I verificación, derivación, testing.
¿Qué es la programación funcional?
Hay diferentes opiniones.
I Es un estilo de programación en el cual el método básico de
computar es aplicar funciones a argumentos
I Un lenguaje de programación funcional es un lenguaje que
permite y alienta el uso de un estilo funcional.
Haskell
I Haskell posee varias ventajas.
I Programas Concisos
I Sistemas de Tipos Poderoso
I Funciones Recursivas
I Fácilidad para probar propiedades de programas.
I Funciones de Alto Orden
I Evaluación Perezosa
I Facilidad para definir DSLs
I Efectos Monádicos
I Haremos un “repaso” por la sintaxis básica de Haskell.
I También introduciremos algunos conceptos nuevos.
Preludio
I Muchas funciones de uso común están definidas en el Preludio
(Prelude.hs)
I Además de las operaciones aritméticas usuales se definen
muchas funciones que operan sobre listas.
I head , tail , (!!), take, drop, length, sum, product, (++), reverse
I Leer el código del preludio puede ser muy instructivo (y
sorprendente!).
GHC
I Usaremos GHC, un compilador (ghc) e intérprete (ghci) de
Haskell, que también soporta varias extensiones del mismo.
I URL: http://www.haskell.org/ghc
I Es conveniente instalar la Haskell Platform, que consiste del
GHC junto con una colección de bibliotecas frecuentemente
usadas.
http://www.haskell.org/ghc
La aplicación de funciones
I en Haskell la aplicación se denota con un espacio y asocia a la
izquierda.
Matemáticas Haskell
f (x) f x
f (x , y) f x y
f (g (x)) f (g x)
f (x , (g (y)) f x (g y)
f (x) g (y) f x ∗ g y
I La aplicación tiene mayor precedencia que cualquier otro
operador.
f x + y = (f x) + y
Nombres y comentarios
I Las funciones y sus argumentos deben empezar con minúscula,
y pueden ser seguidos por cero o más letras (mayúsculas o
minúsculas), d́ıgitos, guiones bajos, y apóstrofes.
I Las palabras reservadas son:
case class data default deriving do else if import in infix
infixl infixr instance let module newtype of then type where
I Los comentarios se escriben
-- comentario que finaliza junto con la ĺınea
{- bloque de comentarios, útil para comentarios
que no entran en una sola ĺınea. -}
Offside Rule
I En una serie de definiciones, cada definición debe empezar en
la misma columna.
a = b + c
where
b = 1
c = 2
d = a + 2
I Gracias a esta regla no hace falta un sintaxis expĺıcita para
agrupar definiciones.
Operadores infijos
I Los operadores infijos son funciones como cualquier otra.
I Una función se puede hacer infija con backquotes
10 ‘div ‘ 4 = div 10 4
I Se pueden definir operadores infijos usando alguno de los
śımbolos disponibles
a ∗∗ b = (a ∗ b) + (a + 1) ∗ (b − 1)
I La asociatividad y precedencia se indica usando infixr
(asociativad der.), infixl (asociatividad izq.), o infix (si los
paréntesis deben ser obligatorios)
infixr 6 (∗∗)
Tipos
I Un tipo es un nombre para una colección de valores
I Ej: Bool contiene los valores True y False.
I Escribimos True :: Bool y False :: Bool .
I En general, si una expresión e tiene tipo t escribimos
e :: t
I En Haskell, toda expresión válida tiene un tipo
I El tipo de cada expresión es calculado previo a su evaluación
mediante la inferencia de tipos.
I Si no es posible encontrar un tipo (por ejemplo (True + 4)) el
compilador/intérprete protestará con un error de tipo.
Tipos básicos
Alguno de los tipos básicos de Haskell son:
I Bool , booleanos
I Char , caracteres
I Int, enteros de precisión fija.
I Integer , enteros de precisión arbitraria.
I Float, números de punto flotante de precisión simple.
Listas
I Una lista es una secuencia de valores del mismo tipo
I [True,True,False,True ] :: [Bool ]
I [’h’, ’o’, ’l’, ’a’] :: [Char ]
I En general, [t ] es una lista con elementos de tipo t.
I t, puede ser cualquier tipo válido.
I [[’a’], [’b’, ’c’], [ ]] :: [[Char ]]
I No hay restricción con respecto a la longitud de las listas.
Tuplas
I Una tupla es una secuencia finita de valores de tipos
(posiblemente) distintos.
I (True,True) :: (Bool ,Bool)
I (True, ’a’, ’b’) :: (Bool ,Char ,Char)
I En general, (t1, t2, ..., tn) es el tipo de una n-tupla cuyas
componente i tiene tipo ti , para i en 1 . . n.
I A diferencia de las listas, las tuplas tienen explicitado en su
tipo la cantidad de elementos que almacenan.
I Los tipos de las tuplas no tiene restricciones
I (’a’, (True, ’c’)):: (Char , (Bool ,Char))
I (([’a’, ’b’], ’a’), ’b’)::(([Char ],Char),Char)
Funciones
I Una función mapea valores de un tipo en valores de otro
I not :: Bool → Bool
I isDigit :: Char → Bool
I En general, Un tipo t1 → t2 mapea valores de t1 en valores de
t2.
I Se pueden escribir funciones con múltiples argumentos o
resultados usando tuplas y listas.
add :: (Int, Int)→ Int
add (x , y) = x + y
deceroa :: Int → [ Int ]
deceroa n = [0 . . n ]
Currificación y aplicación parcial
I Otra manera de tomar múltiples argumentos es devolver una
función comoresultado
add ′ :: Int → (Int → Int)
add ′ x y = x + y
I A diferencia de add , add ′ toma los argumentos de a uno por
vez. Se dice que add ′ está currificada.
I La ventaja de la versión currificada es que permite la
aplicación parcial:
suma3 :: Int → Int
suma3 = add ′ 3
Currificación
I Si queremos expresar una función que tome 3 argumentos
devolvemos una función que devuelve una función:
mult :: Int → (Int → (Int → Int))
mult x y z = x ∗ y ∗ z
I Para evitar escribir muchos paréntesis, por convención el
constructor de tipos → asocia a la derecha.
mult :: Int → Int → Int → Int
I Notar que esta convención es consistente con la aplicación
asociando a la izquierda.
I A menos que la función lo requiera, en Haskell todas las
funciones están currificadas.
Nombres de los tipos
I A excepción de listas, tuplas y funciones, los nombres de los
tipos concretos comienzan con mayúsculas.
I El espacio de nombres de los tipos está completamente
separado del espacio de nombres de las expresiones.
Polimorfismo
I Una función es polimórfica si su tipo contiene variables de
tipo.
length :: [a ]→ Int
Para cualquier tipo a la función length es la misma.
I Las variables de tipo se escriben con minúscula.
I Las variables de tipo pueden ser instanciadas a otros tipos
length [False,True ] ← a = Bool
length [’a’, ’b’] ← a = Char
I A veces se llama polimorfismo paramétrico a este tipo de
polimorfismo.
Sobrecarga de funciones
I ¿Cuál es el tipo de 3 + 2?
I En Haskell, los números y las operaciones aritméticas están
sobrecargadas
I Esta sobrecarga se realiza mediante clases de tipo.
I El operador (+) tiene tipo:
(+) :: Num a⇒ a→ a→ a
I (+) está definido para cualquier tipo que sea una instancia de
la clase Num.
I A diferencia del polimorfismo paramétrico, hay una definición
distinta de (+) para cada instancia.
Clases de tipo
I Haskell provee una serie de clases básicas:
I Eq son los tipos cuyos valores pueden ser comparados para ver
si son iguales o no.
(==) :: Eq a⇒ a→ a→ Bool
(/=) :: Eq a⇒ a→ a→ Bool
¿Qué tipo no puede ser instancia de esta clase?
I Ord son los tipos que además de ser instancias de Eq poseen
un orden total.
(<), (6), (>), (>) :: Ord a⇒ a→ a→ Bool
min,max :: Ord a⇒ a→ a→ a
Clases de tipo
I Show son los tipos cuyos valores pueden ser convertidos en
una cadena de caracteres.
show :: Show a⇒ a→ String
I Read es la clase dual. Son los tipos que se pueden obtener de
una cadena de caracteres.
read :: Read a⇒ String → a
I ¿A qué tipo corresponde la instancia que leerá
I not (read "False")?
I read "3"?
I read "3" :: Int?
Clases de Tipo
I Num son los tipos numéricos
I Sus instancias deben implementar
(+), (−), (∗) :: Num a⇒ a→ a→ a
negate, abs, signum :: Num a⇒ a→ a
¿Y la división?
I Integral son los tipos que son Num e implementan
div ,mod :: Integral a⇒ a→ a→ a
I Fractional son los tipos que son Num e implementan
(/) :: Fractional a⇒ a→ a→ a
recip :: Fractional a⇒ a→ a
Expresiones Condicionales
I Las funciones pueden ser definidas usando expresiones
condicionales
abs :: Int → Int
abs n = if n > 0 then n else− n
I Para que la expresión condicional tenga sentido, ambas ramas
de la misma deben tener el mismo tipo.
I Las expresiones condicionales siempre deben tener la rama
“else”
I Por lo tanto no hay ambigüedades en caso de anidamiento:
signum :: Int → Int
signum n = if n < 0 then− 1 else
if n == 0 then 0 else 1
Ecuaciones con Guardas
I Una alternativa a los condicionales es el uso de ecuaciones con
guardas.
abs n | n > 0 = n
| otherwise = −n
I Se usan para hacer ciertas definiciones más fáciles de leer.
signum n | n < 0 = −1
| n == 0 = 0
| otherwise = 1
I La condición otherwise se define en el preludio como
otherwise = True
Pattern Matching
I Muchas funciones se definen más claramente usando pattern
matching.
not :: Bool → Bool
not False = True
not True = False
I Los patrones se componen de constructores de datos y
variables (salvo los patrones 0 y n + 1) .
I Una variable es un patrón que nunca falla.
succ :: Int → Int
succ n = n + 1
Pattern Matching
I Usando el ingenio se pueden obtener definiciones concisas.
(∧) :: Bool → Bool → Bool
True ∧ True = True
True ∧ False = False
False ∧ True = False
False ∧ False = False
puede ser escrita en forma compacta como
(∧) :: Bool → Bool → Bool
True ∧ True = True
∧ = False
I Notar la importancia del orden de las ecuaciones.
Patrones de tuplas
I Una tupla de patrones es un patrón.
fst :: (a, b)→ a
fst (x , ) = x
snd :: (a, b)→ b
snd ( , y) = y
I ¿Qué hace la siguiente función?
f (x , (y , z)) = ((x , y), z)
I En general, los patrones pueden anidarse
Patrones de Listas
I Toda lista (no vaćıa) se contruye usando el operador (:)
(llamado cons) que agrega un elemento al principio de la lista
[1, 2, 3, 4] 7→ 1 : (2 : (3 : (4 : [ ])))
I Por lo tanto, puedo definir funciones usando el patrón (x : xs)
head :: [a ]→ a
head (x : ) = x
tail :: [a ]→ [a ]
tail ( : xs) = xs
I (x : xs) sólo matchea el caso de listas no vaćıas >head [ ]
Error !
Expresiones Lambda
I Se pueden construir funciones sin darles nombres usando
expresiones lambda.
λx → x + x
I Estas funciones se llaman funciones anónimas.
I En Haskell escribimos \ en lugar de la letra griega lambda λ
I La notación proviene del cálculo lambda, en el cual se basa
Haskell, y que estudiaremos en detalle más adelante.
Utilidad de las expresiones lambda
I Usando lambdas puedo explicitar que las funciones son
simplemente valores:
add x y = x + y
add = λx → (λy → x + y)
I Evito tener que darle un nombre a una función que se usa una
sola vez.
impares n = map f [0 . . n − 1]
where f x = x ∗ 2 + 1
odds n = map (λx → x ∗ 2 + 1) [0 . . n − 1]
Secciones
I Un operador infijo, puede ser escrito en forma prefija usando
paréntesis:
> (+) 1 2
3
I También uno de los argumentos puede ser inclúıdo en los
paréntesis
> (1+) 2
3
> (+2) 1
3
I En general, dado un operador ⊕, entonces las funciones de la
forma (⊕), (x⊕), (⊕y) son llamadas secciones.
Conjuntos por comprensión
I En matemáticas, una manera de construir conjuntos a partir
de conjuntos existentes es con la notación por comprensión
{x2|x ∈ {1 . . . 5}}
describe el conjunto {1, 4, 9, 16, 25} o (lo que es lo mismo) el
conjunto de todos los números x2 tal que x sea un elemento
del conjunto {1 . . . 5}
Listas por comprensión
I En Haskell, una manera de construir listas a partir de listas
existentes es con la notación por comprensión
[x ↑ 2 | x ← [1 . . 5]]
describe la lista [1, 4, 9, 16, 25] o (lo que es lo mismo) la lista
de todos los números x ↑ 2 tal que x sea un elemento de la
lista [1 . . 5]
I La expresión x ← [1 . . 5] es un generador, ya que dice como
se generan los valores de x .
I Una lista por comprensión puede tener varios generadores,
separados por coma.
> [(x , y) | x ← [1, 2, 3], y ← [4, 5]]
[(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)]
I ¿Qué pasa cuando cambiamos el orden de los generadores?
> [(x , y) | y ← [4, 5], x ← [1, 2, 3]]
I Los generadores posteriores cambian más rápidamente.
Generadores dependientes
I Un generador puede depender de un generador anterior
[(x , y) | x ← [1 . . 3], y ← [x . . 3]]
Esto es la lista de todos los pares (x , y) tal que x , y están en
[1 . . 3] e y > x .
I ¿Qué hace la siguiente función?
concat :: [[a ]]→ [a ]
concat xss = [x | xs ← xss, x ← xs ]
> concat [[1, 2, 3], [4, 5], [6]]
[1, 2, 3, 4, 5, 6]
Guardas
I Las listas por comprensión pueden usar guardas para restringir
los valores producidos por generadores anteriores
[x | x ← [1 . . 10], even x ]
I ¿Qué hace la siguiente función?
factors :: Int → [ Int ]
factors n = [x | x ← [1 . . n ], n ‘mod ‘ x == 0]
I Como un número n es primo iff sus únicos factores son 1 y n,
podemos definir
prime :: Int → Bool
prime n = factors n == [1, n ]
primes :: Int → [ Int ]
primes n = [x | x ← [2 . . n ], prime x ]
Cadenas
I Una String es una lista de caracteres.I "Hola" :: String
I "Hola" = [’H’, ’o’, ’l’, ’a’]
I Todas las funciones sobre listas son aplicables a String , y las
listas por comprensión pueden ser aplicadas a Strings.
cantminusc :: String → Int
cantminusc xs = length [x | x ← xs, isLower x ]
Zip
I La función zip, mapea dos listas a una lista con los pares de
elementos correspondientes
zip :: [a ]→ [b ]→ [(a, b)]
> zip [’a’, ’b’, ’c’] [1, 2, 3, 4]
[(’a’, 1), (’b’, 2), (’c’, 3)]
I Ejemplo: Lista de pares de elementos adyacentes:
pairs :: [a ]→ [(a, a)]
pairs xs = zip xs (tail xs)
I ¿Está una lista ordenada?
sorted :: Ord a⇒ [a ]→ Bool
sorted xs = and [x 6 y | (x , y)← pairs xs ]
Ejemplo zip: pares ı́ndice/valor
I Podemos usar zip para generar ı́ndices
rangeof :: Int → Int → [a ]→ [a ]
rangeof low hi xs = [x | (x , i)← zip xs [0 . .],
i > low ,
i 6 hi ]
> [x ↑ 2 | x ← [1 . . 10]]
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
> rangeof 3 7 [x ↑ 2 | x ← [1 . . 10]]
[16, 25, 36, 49, 64]
Recursión
I En los lenguajes funcionales, la recursión es uno de los
principales recursos para definir funciones.
factorial :: Int → Int
factorial 0 = 1
factorial n = n ∗ factorial (n − 1)
I ¿Qué sucede con factorial n cuando n < 0?
I Recursión sobre listas
length :: [a ]→ Int
length [ ] = 0
length (x : xs) = 1 + length xs
Recursión Mutua
I No hace falta ninguna sintaxis especial para la recursión
mutua.
zigzag :: [(a, a)]→ [a ]
zigzag = zig
zig [ ] = [ ]
zig ((x , ) : xs) = x : zag xs
zag [ ] = [ ]
zag (( , y) : xs) = y : zig xs
I > zigzag [(1, 2), (3, 4), (5, 6), (7, 8)]
[1, 4, 5, 8]
Quicksort
I El algoritmo de ordenación Quicksort:
I La lista vaćıa está ordenada
I Las listas no vaćıas pueden ser ordenadas, ordenando los
valores de la cola 6 que la cabeza, ordenando los valores >
que la cabeza y rearmando el resultado con las listas
resultantes a ambos lados de la cabeza.
I Su implementación:
qsort :: Ord a⇒ [a ]→ [a ]
qsort [ ] = [ ]
qsort (x : xs) = qsort chicos ++ [x ] ++ qsort grandes
where chicos = [a | a← xs, a 6 x ]
grandes = [b | b ← xs, b > x ]
Referencias
I “Can Programming Be Liberated from the von Neumann
Style?”. John Backus, Turing Award Lecture. 1977
I Why Functional Programming Matters. John Hughes,
Computing Journal. Vol 32. 1989.
I Programming in Haskell. Graham Hutton, CUP 2007.
I Introducción a la Programación Funcional con Haskell.
Richard Bird, Prentice Hall 1997.
	Programación Funcional
	Programación Funcional
	Haskell
	Sintaxis
	Tipos
	Expresividad
	Listas
	Listas Por comprensión
	Cadenas
	Zip
	Recursión