Programación en Haskell

Importante: el subconjunto de Haskell del sitio incluye ecuaciones con patrones y guardas, where, let, case, if, lambdas, secciones, listas, rangos, comprensiones, tuplas y tipos de datos propios (data). No modela el sistema de tipos (las firmas se leen y se ignoran), las clases de tipos ni la entrada y salida. Los fragmentos de otros lenguajes (Java, Scheme, Clojure, F#, Scala) son afirmaciones didácticas: la página no los ejecuta.

Objetivo de aprendizaje

Al concluir este tema, el estudiante será capaz de:

1. Leer un programa sencillo en Haskell: definiciones, firmas de tipo, ecuaciones y patrones.
2. Escribir funciones por casos con emparejamiento de patrones, guardas y definiciones locales.
3. Definir tipos de datos algebraicos propios y funciones que los consumen, y comparar ese estilo con las jerarquías de clases de la Unidad III.
4. Resolver problemas con recursión sobre listas y árboles, usando estructuras inmutables.
5. Reconocer la misma función en lenguajes funcionales distintos y explicar qué cambia y qué permanece.

Ruta de trabajo del tema

1. Planteamiento inicial

El factorial de n se define como n! = n · (n − 1) · … · 1, con 0! = 1. Observe tres maneras de escribirlo.

En Java (afirmación didáctica; no se ejecuta):

static long factorial(int n) {
    long resultado = 1;
    for (int i = 2; i <= n; i++) {
        resultado = resultado * i;
    }
    return resultado;
}

En Python, con recursión:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

En Haskell:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

Esta hipótesis se retomará en la sección 3.

2. Anatomía de un programa en Haskell

Un programa Haskell es una colección de definiciones. Cada definición es una igualdad: el nombre de la izquierda es igual a la expresión de la derecha.

Leer una firma de tipo

La firma es documentación que el compilador verifica. Se lee de izquierda a derecha; la última parte es lo que devuelve.

Definición — Variable de tipo: letra minúscula (a, b) en una firma que representa cualquier tipo. Una función con variables de tipo es polimórfica: length :: [a] -> Int mide listas de números, de textos o de lo que sea. Es el polimorfismo paramétrico que se estudió en la Unidad III.

Python y Haskell, lado a lado:

El factorial, línea por línea

-- Firma: recibe un Integer (entero de precisión arbitraria) y devuelve un Integer.
factorial :: Integer -> Integer
-- Ecuación 1: el caso base. El patrón es el literal 0.
factorial 0 = 1
-- Ecuación 2: el caso general. «n» es una variable que se liga al argumento.
factorial n = n * factorial (n - 1)

Observe cómo se evalúa factorial 4 con la estrategia estricta: los productos quedan pendientes dentro de la expresión hasta llegar al caso base, y luego se resuelven de adentro hacia afuera.

3. Patrones, guardas y definiciones locales

Emparejamiento de patrones

Una función se define por casos. Cada ecuación tiene patrones en lugar de parámetros; Haskell prueba las ecuaciones en orden y usa la primera cuyos patrones coinciden con los argumentos.

Retome el planteamiento inicial: en Python, el caso base se separa con un if dentro del cuerpo; en Haskell, se separa en la definición misma, con una ecuación por caso. Esa es la diferencia de estilo más visible.

Guardas

Cuando la decisión depende de una condición y no de la forma del dato, se usan guardas: cada una es una condición booleana, y se usa la primera que se cumple. otherwise siempre se cumple.

clasificar :: Int -> String
clasificar n
  | n < 0 = "negativo"
  | n == 0 = "cero"
  | otherwise = "positivo"

Definiciones locales con where

where permite dar nombre a cálculos intermedios dentro de una definición. Las definiciones locales se comparten: se evalúan una sola vez aunque se usen varias veces.

hipotenusa :: Double -> Double -> Double
hipotenusa a b = sqrt suma
  where suma = cuadrado a + cuadrado b
        cuadrado x = x * x

Nota — where frente a let: where se escribe después de la definición y sus nombres valen en todo el cuerpo (incluidas las guardas); let … in … es una expresión: define nombres y los usa en el cuerpo que sigue a in. Hacen lo mismo; se elige la que se lea mejor.

4. Recursión y listas: ordenar y filtrar

Con el emparejamiento de patrones y la recursión del tema 4.0 se escriben algoritmos completos en pocas líneas. El ejemplo clásico es quicksort: ordenar una lista es ordenar los menores que el primer elemento (el pivote), colocar el pivote, y ordenar los demás.

quicksort :: [Int] -> [Int]
quicksort [] = []
quicksort (p:xs) = quicksort [x | x <- xs, x < p] ++ [p] ++ quicksort [x | x <- xs, x >= p]

Compare esta definición con la versión de Python. Las dos hacen lo mismo; observe qué es más corto y qué más explícito.

La criba de Eratóstenes

La evaluación perezosa permite escribir los números primos como una lista infinita, y usar solo los primeros.

primos :: [Int]
primos = criba [2 ..]

-- Se queda con el primer número (es primo) y descarta de los demás los múltiplos de él.
criba :: [Int] -> [Int]
criba (p:xs) = p : criba [x | x <- xs, x `mod` p /= 0]

5. Tipos de datos propios

Hasta ahora se usaron los tipos incorporados. Haskell permite definir tipos nuevos enumerando sus variantes con data. Cada variante tiene un constructor (con inicial mayúscula) que puede llevar campos.

Definición — Tipo de datos algebraico: tipo definido por una lista de variantes (constructores), cada una con sus campos. Un valor del tipo es una de las variantes. Se consume con emparejamiento de patrones: una ecuación por variante.

-- Un tipo con dos variantes: un círculo (con su radio) o un rectángulo (con base y altura).
data Forma = Circulo Double | Rect Double Double

-- Una ecuación por variante.
area :: Forma -> Double
area (Circulo r) = 3.0 * r * r
area (Rect b h) = b * h

En Python, sin tipos algebraicos, se emulan con datos etiquetados y una función que decide por la etiqueta:

Dos maneras de organizar el mismo programa

En la Unidad III, las formas se resolvieron con clases: una clase base Forma y una subclase por variante, cada una con su método area. En este tema se resolvieron con un tipo y una función por casos. Son dos organizaciones del mismo programa, y cada una facilita una clase distinta de cambio:

Nota: ninguna es «mejor»: es un compromiso. Se conoce como el problema de la expresión. Si se espera agregar muchos tipos nuevos, conviene la organización por clases; si se espera agregar muchas operaciones, conviene la funcional.

6. Árboles inmutables

Un árbol binario de búsqueda es o vacío (Hoja) o un nodo con un valor y dos subárboles: todos los valores del subárbol izquierdo son menores, y los del derecho, mayores. Se define con un tipo propio, y las dos operaciones fundamentales son dos funciones por casos.

-- Un árbol es una hoja (vacío) o un nodo con subárbol izquierdo, valor y subárbol derecho.
data Arbol = Hoja | Nodo Arbol Int Arbol

-- Insertar NO modifica el árbol: devuelve un árbol nuevo.
insertar :: Int -> Arbol -> Arbol
insertar x Hoja = Nodo Hoja x Hoja
insertar x (Nodo izq v der)
  | x < v = Nodo (insertar x izq) v der
  | x > v = Nodo izq v (insertar x der)
  | otherwise = Nodo izq v der

-- Recorrer en orden produce la lista ordenada.
aLista :: Arbol -> [Int]
aLista Hoja = []
aLista (Nodo izq v der) = aLista izq ++ [v] ++ aLista der

Definición — Estructura inmutable en la práctica: «actualizar» una estructura inmutable es una función que devuelve la versión nueva. Como las versiones comparten estructura, la actualización de un árbol equilibrado cuesta lo mismo que en uno mutable en orden de magnitud (proporcional a la altura), sin perder la versión anterior. Las bibliotecas de Haskell (Data.Map, Data.Set) se apoyan en esta idea.

7. Otros lenguajes funcionales

Haskell no es el único. La familia funcional es amplia, y todos comparten lo esencial (funciones como valores, composición, inmutabilidad por omisión) con distinta sintaxis y distintas decisiones de diseño.

El mismo programa, la suma de los cuadrados de los pares, en seis lenguajes. Observe qué cambia (la sintaxis) y qué permanece (la estructura: filtrar, transformar, combinar).

Reconozca ahora la sintaxis de cada lenguaje.

8. Errores conceptuales frecuentes

Error común: escribir en Haskell con paréntesis y comas como en Python: suma(1, 2). En Haskell se escribe suma 1 2; con paréntesis y coma se está pasando una tupla.

Error común: poner el caso general antes del caso base. Las ecuaciones se prueban en orden: factorial n antes de factorial 0 capturaría todos los valores.

Error común: olvidar que las listas de Haskell tienen un solo tipo: [1, "a"] no es válida. Para mezclar tipos se usan tuplas o tipos de datos propios.

Error común: pensar que, sin variables que cambian, no pueden resolverse problemas «con estado». Se resuelven pasando el estado como argumento y devolviendo el nuevo.

Error común: querer «modificar» un árbol o una lista. Se construye uno nuevo; el anterior sigue disponible.

9. Libreta de trabajo

10. Preguntas de reflexión

1. Escriba en Haskell, con dos ecuaciones, una función que cuente cuántos elementos tiene una lista. Indique el caso base y qué hace el caso recursivo con la cabeza y con la cola.
2. Defina un tipo Figura con tres variantes y una función que calcule el perímetro. ¿Qué tendría que modificar para agregar una variante nueva? ¿Y para agregar una operación nueva?
3. Compare las ventajas de que un compilador verifique las firmas antes de ejecutar con la flexibilidad de Python. ¿En qué tipo de proyecto preferiría cada una?
4. En el árbol de búsqueda, ¿por qué insertar no necesita copiar todo el árbol? Relacione la respuesta con la compartición estructural del tema 4.1.
5. Elija uno de los lenguajes de la tabla de la sección 7 e investigue en qué se usa en la industria. ¿Qué rasgo del lenguaje explica ese uso?

11. Lecturas recomendadas

• Lipovača, M. (2011). Learn you a Haskell for great good! No Starch Press. (Disponible libremente en learnyouahaskell.com.)
• Hutton, G. (2016). Programming in Haskell (2nd ed.). Cambridge University Press.
• Bird, R. (2015). Thinking functionally with Haskell. Cambridge University Press. (En la bóveda: 08-Referencias.)
• Abelson, H., & Sussman, G. J. (1996). Structure and interpretation of computer programs (2nd ed.). MIT Press. (Libre en línea; uso de Scheme.)
• Sebesta, R. (2015). Concepts of programming languages (11th ed.), capítulo sobre lenguajes de programación funcional. Pearson.
• Wadler, P. (1998). The expression problem. Nota distribuida en la lista java-genericity. (Origen del nombre «problema de la expresión».)