Una Introducción agradable a Haskell
anterior siguiente inicio


3  Funciones

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

3.1  Abstraciones lambda

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.

3.2  Operadores Infijos

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)

3.2.1  Secciones

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

3.2.2  Declaraciones de infixidad

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

3.3  Las Funciones son no estrictas

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.

3.4  Estructuras de datos "Infinitas"

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.

Fib Example

Figura 1

Otra aplicaciones de listas infinitas pueden verse en la Sección 4.4.

3.5  La función Error

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