Una Introducción agradable a Haskell
anterior siguiente
inicio
Ya que Haskell es un lenguaje funcional, podemos esperar que las funciones jueguen un papel esencial, como veremos seguidamente. Es esta sección, trataremos varios aspectos de las funciones en Haskell.
En primer lugar, consideremos la siguiente definción de
función que suma sus dos argumentos:
add :: Integer -> Integer -> Integer
add x y = x + y
Este es un ejemplo de función parcializada (curried).
(El origen del nombre curry proviene de la persona que
popularizó el uso de la parcialización: Haskell Curry. Para
capturar la función anterior en forma no parcializada (uncurried),
podemos usar una tupla, como en:
add (x,y) = x + y
¡Pero entonces tal versión de add es realmente
una función de un solo argumento! Una aplicación de add
tiene la forma add e1 e2, y
es equivalente a (add e1) e2,
ya que la aplicación de funciones es asociativa a la izquierda.
En otras palabras, al aplicar add a un argumento se
obtiene una nueva función que puede ser aplicada al segundo
argumento. Esto es consistente con el tipo de add, Integer->Integer->Integer,
ya que éste es equivalente a Integer->(Integer->Integer); es
decir, -> es asociativo a la derecha. Además,
usando add, podemos definir inc de forma
distinta a la anterior:
inc = add 1
Este es un ejemplo de aplicación parcial de
una función parcializada, y constituye un ejemplo de cómo
podemos devolver una función como un valor. Consideremos ahora
el caso en el que pasamos una función como argumento. La bien
conocida función map constituye un ejemplo perfecto:
map :: (a->b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
[La aplicación tiene mayor precedencia que cualquier
operator infijo, y por tanto la segunda ecuación debe entenderse
en la forma (f x) : (map f xs).]
La función map es polimórfica y su tipo indica
claramente que su primer argumento es una función; nótese que
las dos a's deben ser instanciadas al mismo tipo (e
igualmente para las b's). Como ejemplo de uso de map,
podemos incrementar los elementos de una lista:
map (add 1) [1,2,3] => [2,3,4]
Estos ejemplos muestran la naturaleza de primera-categoría que tienen las funciones, que se llaman funciones de orden superior al ser usadas de la forma anterior.
En lugar de usar ecuaciones para definir funciones, podemos
definirlas en forma "anónima" vía una lambda
abstración. Por ejemplo, podemos escribir una función
equivalente a inc en la forma \x -> x+1.
Del mismo modo, la función add es equivalente a \x -> \y -> x+y.
Las lambda abstracciones anidadas pueden escribirse en la
siguiente otra forma equivalente \x y -> x+y.
De hecho, las ecuaciones:
inc x = x+1
add x y = x+y
son formas abreviadas de:
inc = \x -> x+1
add = \x y -> x+y
Más tarde veremos algo más sobre tales equivalencias.
En general, si x tiene por tipo t1 y exp tiene por tipo t2, entonces \x->exp tiene por tipo t1->t2.
Los operadores infijos son también funciones, y pueden
definirse a través de ecuaciones. Por ejemplo, tenemos la
siguiente definición para el operador de concatenación:
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs++ys)
[Desde el punto de vista léxico, los operadores infijos
consisten únicamente de "símbolos", al contrario que
los identificadores normales que son alfanuméricos (§2.4). Haskell no permite
operadores prefijos, salvo el operador menos (-), que
simultánemaente es infijo y prefijo.]
Otro ejemplo de operator infijo importante es la composición
de funciones:
(.) :: (b->c) -> (a->b) -> (a->c)
f . g = \ x -> f (g x)
Puesto que los operadores infijos son funciones, tiene sentido parcializarlas. En Haskell, la aplicación parcial de un operador infijo se llama una sección. Por ejemplo:
| (x+) | = | \y -> x+y |
| (+y) | = | \x -> x+y |
| (+) | = | \x y -> x+y |
[Los paréntesis son obligatorios.]
La última forma de sección devuelve la función equivalente al operador infijo, y permite pasar un operador infijo como argumento de una función, como por ejemplo en map (+) [1,2,3] (¡el lector deberá verificar que la última expresión devuelve una lista de funciones!). También es necesario el uso de los paréntesis al dar el tipo de los operadores infijos, como vimos en los ejemplos correspondientes a (++) y (.).
Ahora vemos que add es precisamente (+), y inc
es (+1). Por ello, las siguientes definiciones son
correctas:
inc = (+ 1)
add = (+)
Podemos asociar un operador infijo a un valor funcional, ¿y al revés? Sí --- para ello simplemente escribimos su identificador entre apóstrofes. Por ejemplo, x `add` y es lo mismo que add x y. (Nótese que add es orlado de apóstrofes, no comillas simples como las usadas para denotar caracteres; es decir, 'f' es un carácter, mientras que `f` es un operador infijo. Afortunadamente, la mayoría de los terminales ASCII distinguen las fuentes usadas en este manuscrito.) Algunas funciones se leen mejor de esta forma. Un ejemplo es el predicado predefinido elem que comprueba la pertenencia; la expresión x `elem` xs puede leerse como "x es un elemento de xs."
[Existen otras reglas sintácticas especiales para secciones que afectan a los operadores - (§3.5,§3.4).]
En este punto, el lector puede estar sorprendido sobre la cantidad de posibilidades para definir funciones. La decisión de proporcionar tantos mecanismo es histórica, y refleja parcialmente este deseo por consistencia (por ejemplo, infixidad versus funciones ordinarias).
Para cualquier operador o constructor podemos dar una declaración
de infixidad (incluidos aquellos que corresponden a
identificadores literales, como `elem`). Esta
declaración especifica un nivel de precedencia de 0 to 9 (0 el
menor; la aplicación tiene el mayor nivel de precedencia: 10), y
una indicación de su asociatividad. Por ejemplo, las
declaraciones de infixidad para ++ y . son:
infixr 5 ++
infixr 9 .
Ambas especifican asociatividad a la derecha, la primera con
un nivel de precedencia 5, y 9 para la otra. La asociatividad a
la izquierda se especifica con infixl, y la
no-asociatividad con infix. También podemos declarar
varios operadores con la misma declaración de infixidad. Si no
se especifica la infixidad de un operador particular, ésta se
toma por defecto como infixl 9. (Ver en §4.4.2 una definición
detallada de las reglas de asociatividad.)
Sea bot definida en la forma:
bot = bot
Es decir, bot es una expresión que no termina. En
sentido abstracto, podemos denotar con _|_ (leido
"bottom") el valor de una expresión que no termina. Las expresiones que devuelven algún tipo de error
en ejecución, tal como 1/0, también tendrán este
valor. Tal error es no recuperable: los programas no pueden
continuar si se produce este error. Otros errores detectados por
el sistema de E/S, tal como un error producido por
"fin-de-fichero", son recuperables y son tratados de
forma distinta. (Tal error de E/S no es realmente un error, sino
una "excepción". Pueden verse más detalles sobre
excepciones en la Sección 7.)
Una función f se dice estricta si, al ser
aplicada a una expresión sin terminación, tampoco termina. En
otras palabras, f es estricta si el valor de f bot
is _|_. En la mayoría de los lenguajes de programación todas
las funciones son estrictas. Pero este no es el caso de Haskell.
Como ejemplo simple, consideremos const1, la función
constante igual a 1, definida por:
const1 x = 1
En Haskell, el valor de const1 bot es 1.
Operacionalmente hablando, ya que const1 no
"necesita" el valor de su argumento, el sistema nunca
intentará evaluarlo, y no se produce un cómputo sin
terminación. Por esta razón, las funciones no estrictas se
llaman "perezosas", y sus argumentos son evaluados en
forma "perezosa" o por necesidad.
Puesto que un error y una expresión que no termina son semánticamente iguales en Haskell, el razonamiento anterior también sirve para los errores. Por ejemplo, const1 (1/0) también será evaluada a 1.
Las funciones no estrictas son muy poderosas en varias aplicaciones. La principal ventaja es que liberan al programador de algunas consideraciones sobre el orden de evaluación. Podemos pasar valores que contienen gran cantidad de cómputo como argumentos sin preocuparnos de los cómputos que necesitan realizarse. Un ejemplo importante son las estructuras de datos infinitas.
Otra forma de describir las funciones no estrictas es el hecho
de que los cómputos de Haskell se describen a través de
definiciones, al contrario que las asignaciones presentes
en los lenguajes tradicionales. Leeremos la siguiente
declaración
v = 1/0
como "definimos v como 1/0" en
lugar de "computar 1/0 y memorizar el resultado en v".
La división por cero dará un error únicamente en el caso de
que el valor de v sea necesario. Por la misma razón,
tal declaración no implica cómputos. Las asignaciones se
realizan en forma ordenada: el significado depende del orden en
que se realicen. Sin embargo, las definiciones pueden presentarse
en cualquier orden sin cambiar el significado.
Una ventaja de la naturaleza no estricta de Haskell es que los constructores de datos tampoco son estrictos. Esto no deberá sorprendernos ya que los constructores constituyen una clase especial de funciones (la diferencia es que pueden utilizarse en la comparación de patrones). Por ejemplo, el constructor de listas (:) no es estricto.
Los constructores no-estrictos permiten definir
(conceptualmente) estructuras de datos infinitas.
Presentamos alguna de ellas:
ones = 1 : ones
Más interesante es la función numsFrom:
numsFrom n = n : numsFrom (n+1)
de forma que numsFrom n es la lista infinita
de los enteros a partir de n. Con ésta podemos
construir una lista infinita de cuadrados:
squares = map (^2) (numsfrom 0)
(nótese el uso de una sección de ^, el operador
infijo exponenciación.)
Naturalmente, eventualmente podemos pensar en extraer un trozo finito de la lista, y para ello existen una colección de funciones predefinidas en Haskell: take, takeWhile, filter, y otras. La definición de Haskell incluye un conjunto amplio de funciones y tipos predefinidos -- éste es llamado "Standard Prelude". El Prelude completo aparece en el Appendix A del Informe; ver el trozo denominado PreludeList con objeto de inspeccionar algunas funciones útiles que trabajan sobre listas. Por ejemplo, take extrae los primeros elementos de una lista:
take 5 squares => [0,1,4,9,16]
La definición anterior de ones es una lista circular. En la mayoría de los casos la perezosidad tiene un impacto importante en la eficiencia, ya que una implementación deberá representar tales listas como una estructura circular, con objeto de economizar espacio de memoria.
Otro ejemplo de uso de circularidad es la secuencia infinita
de la sucesión de Fibonacci computada eficientemente a través
de:
fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]
donde zip es una función del Standard Prelude que
devuelve una mezcla uno a uno de dos listas:
zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip xs ys = []
Nótese que fib, una lista infinita, aparece
definida en términos de ella misma, como si se "mordiera la
cola." Por ello, podemos dibujar su cómputo como se muestra
en la Figura 1.
Otra aplicaciones de listas infinitas pueden verse en la Sección 4.4.
Haskell dispone de una función predefinida llamada error y cuyo tipo es String->a. Es una función singular: de su tipo vemos que devuelve un valor de un tipo polimórfico sin ninguna información adicional, ya que no tiene un argumento que decida el tipo del resultado.
De hecho, existe un valor "compartido" por todos los tipos: _|_. Por supuesto, esto significa semánticamente que éste es el valor devuelto por error (recordemos que todos los errores tienen el mismo valor _|_).
Además, cualquier implementación razonable debería imprimir
la cadena de caracteres argumento de error con objetivos
informativos. Esta función es útil si queremos terminar un
programa cuando algo "fue mal". Por ejemplo, la
definición de head tomada del Standard Prelude es:
head (x:xs) = x
head [] = error "head{PreludeList}: head []"
Una Introducción agradable a Haskell
anterior siguiente inicio