Programación funcional en haskell

Programaci´n Funcional en Haskell
o
Paradigmas de Lenguajes de Programaci´n
o
1◦ cuatrimestre 2006

1.

Expresiones, valores y tipos

Un programa en lenguaje funcional consiste en definir expresiones que
computan (o denotan) valores. As´ como los valores, en el mundo “real” o
ı
“matem´tico”, pertenecen a un conjunto, las expresiones pertenecen a un
a
tipo.
Veamos qu´ tipos puedentener las expresiones de Haskell:
e
Tipos b´sicos como Int, Char, Bool, etc.
a
Funciones , como a → Int, Bool → (Bool → Bool), etc.
Tuplas de cualquier longitud. Por ejemplo, (2 ∗ 5 +1, 4 >0) es de tipo
(Int, Bool).
Listas , secuencias ordenadas de elementos de un mismo tipo, con repeticiones. [Int] representa el tipo lista de enteros, [Bool] es una lista
de booleanos, etc. Las expresionesde tipo lista se construyen con []
(que representa la lista vac´ y : (a:as es la lista que empieza con el
ıa)
elemento a y sigue con la lista as). Tambi´n pueden escribirse entre
e
corchetes, con los elementos separados por comas:
[] :: [Bool]
[3] :: [Int]
’a’ : (’b’ : (’c’ : [])) :: [Char]
[2 > 0, False, ’a’ = ’b’] :: [Bool]
=
[[], [1], [1,2]] :: [[Int]]

El tipo String es sin´nimode [Char], y las listas de este tipo se pueden
o
escribir entre comillas: "plp" es lo mismo que [’p’, ’l’, ’p’].
Tipos definidos por el usuario , con la cl´usula data. Los valores asoa
ciados a estos tipos consisten de un constructor (que se escribe con
may´scula) acompa˜ado de 0 o m´s argumentos.
u
n
a
data Dia = Lunes | Martes | Miercoles | Jueves | Viernes

1

Este tipo tiene cincoconstructores, todos sin argumentos. A esta clase
de tipos se los llama enumerados.
data Either a b = Left a | Right b
data Maybe a = Nothing | Just a

Los tipos pueden tener argumentos, lo que los convierte en tipos param´tricos. Tipos como los de arriba suelen llamarse sumas o uniones,
e
porque pueden representar la uni´n de varios tipos. En particular,
o
Either representa la uni´n dedos tipos cualesquiera, y Maybe repreo
senta el mismo conjunto que su argumento, m´s un valor: Nothing.
a
Left True :: Either True a
Just 3 :: Maybe Int
data BinTree a = Nil | Branch a (BinTree a) (BinTree a)

Ac´ vemos que algunos de los constructores pueden tener como argua
mento el mismo tipo que determinan. Tipos as´ se suelen llamar tipos
ı
recursivos. En este caso, BinTree arepresenta el tipo de los ´rboles
a
binarios cuyos nodos tienen un elemento de a.
Nil :: BinTree a
Branch True Nil
(Branch (4 > 0) Nil
Nil) :: BinTree Int

Las funciones sobre tipos construidos con la cl´usula data pueden dea
finirse por pattern matching. Un patr´n consiste de un constructor con
o
tantas variables como argumentos tenga; al evaluar la funci´n en un
o
argumento, se intentaestablecer una correspondencia entre ´l y cada
e
patr´n, reduciendo en la primera ecuaci´n donde se la encuentre.
o
o
proximo
proximo
proximo
proximo
etc.

:: Dia → Dia
Lunes = Martes
Martes = Miercoles
Miercoles = Jueves

aInt :: (Either Bool Int) → Int
aInt (Left x) = if x then 1 else 0
aInt (Right x) = x
esVacio :: BinTree a b → Bool
esVacio Nil = True
esVacio (Branch _ _ _) =False

Cuando las variables no se usan en el lado derecho de la ecuaci´n, se
o
pueden reemplazar por un _.

2

Los tipos que permiten acceder a sus constructores y hacer pattern
matching se llaman tipos algebraicos. ¡Los booleanos, las tuplas y las
listas tambi´n son tipos algebraicos!
e
fst :: (a, b) → a
fst (x, y) = x
length :: [a] → Int
length [] = []
length (x:xs) = 1 + lengthxs

2.

Currificaci´n y evaluaci´n parcial
o
o
Currificaci´n es una correspondencia entre:
o
funciones que reciben m´ltiples argumentos y devuelven un resultado
u
suma :: (Int, Int) → Int
suma (x, y) = x + y

funciones que reciben un argumento y devuelven una funci´n intermeo
dia que completa el trabajo
suma :: Int → Int → Int
suma x y = x + y

En este ejemplo, suma x es una...