Este post es la lección de verdad del capítulo 1 de HPFP — lambda calculus desde cero, con todas las paradas que la primera noche que hicimos esto con Pascual nos saltamos por las prisas. Contiene explicaciones, demostraciones a mano, y al final los ejercicios para que tú —quien me leas— hagas crujir la materia con tus propios dedos.

Cada sección tiene su propio audio narrado al final, con voz Álvaro de Microsoft Edge. Si prefieres escuchar la explicación mientras vas en el metro, dale al play. Si prefieres leer y mirar las reducciones con calma, ignora el reproductor. Las dos formas valen.

Por qué empezamos por aquí

La mayoría de tutoriales de Haskell empiezan con Hello World y la sintaxis del lenguaje. Después de unos capítulos sueltan functor o monad, suena místico y muchos abandonan.

Allen y Moronuki —los autores de HPFP— hacen otra cosa. Su capítulo 1 no toca Haskell. Toca lambda calculus, el sistema que inventó Alonzo Church en los años treinta antes de que existieran los ordenadores y que resulta ser el corazón teórico de Haskell. La razón es simple: si entiendes lambda calculus, todo lo que viene después deja de ser magia. Cuando veas un functor, ya no será una palabra rara — será un patrón sobre lambdas que reconocerás. Cuando llegues a las mónadas, no te pillará desprevenido — serán otro patrón sobre lambdas.

Lambda calculus tiene una virtud única: se puede aprender a mano. No hay ordenador, no hay sintaxis rara, no hay compilador que te grite. Solo papel, boli, y una regla. Eso lo hace el lugar más justo para empezar — todos llegamos con la misma desventaja y la misma ventaja: cero.

Las tres piezas

Lambda calculus tiene solo tres cosas. Tres. Toda la informática que existe se puede expresar con tres cosas:

1. Variables — letras: x, y, z.
2. Funciones —también llamadas /abstracciones/—, una forma de definir una función anónima.
3. Aplicaciones — una forma de "usar" una función con un argumento.

Ya está. No hay más. No hay if, no hay bucles, no hay clases, no hay tipos siquiera en la versión original. Solo eso.

La pieza nueva, la que no habías visto antes en matemáticas escolares, es la función. En matemáticas normales escribes:

f(x) = x + 1

Eso define una función con nombre —~f~— que toma x y devuelve x+1.

En lambda calculus, escribes la función sin nombre, así:

λx.x+1

Se lee: "la función que, dado un x, devuelve x+1".

La sintaxis tiene tres partes:

• La lambda λ — indica "esto es una función anónima".
• El parámetro x — el nombre que le vamos a dar al argumento que entre.
• El cuerpo x+1 — lo que devuelve la función, después del punto.

Y aplicar una función a un argumento se hace simplemente poniéndolos juntos, con espacio. Igual que en Haskell. Aplicar λx.x+1 al número 3 se escribe:

(λx.x+1) 3

En Haskell esa misma lambda se escribe casi igual, cambiando λ por \ —backslash, porque los teclados normales no tienen lambda—:

\x -> x + 1

Cuando veas una expresión que empieza por backslash en Haskell, estás viendo una lambda. Esa es la sintaxis equivalente.

La regla mágica — beta reducción

Cuando aplicas una lambda a un argumento, sustituyes el parámetro por el argumento en el cuerpo. Eso es todo. Esa operación se llama beta reducción y es literalmente la única regla de cálculo del lambda calculus.

Vamos a hacer tres reducciones lentas, con todos los pasos visibles, y así interiorizas el patrón.

Ejemplo uno — la identidad

(λx.x) 5

Léelo en voz alta: "la función lambda x punto x, aplicada a cinco". Su cuerpo es x. Sustituyo x por 5:

(λx.x) 5
→ 5

La función λx.x devuelve tal cual lo que le metas. Se llama función identidad y es la lambda más simple que existe. En Haskell viene incorporada con el nombre id.

Ejemplo dos — sumar uno

(λx.x+1) 7

El cuerpo es x+1. Sustituyo x por 7:

(λx.x+1) 7
→ 7+1
→ 8

Dos pasos: primero la sustitución del parámetro, luego la evaluación aritmética. En lambda calculus puro no habría aritmética, pero para que se vean los pasos claros usamos números de toda la vida.

Ejemplo tres — dos argumentos por currying

Lambda calculus solo soporta funciones de un argumento. Si quieres una función de dos, anidas dos lambdas. La función "sumar dos números" se escribe así:

λx.λy.x+y

Que se lee: "la función que toma x y devuelve OTRA función que toma y y devuelve x+y". Eso es exactamente el currying que verás en Haskell.

Para aplicarla a dos argumentos —digamos 3 y ~4~— hay que aplicar uno detrás de otro, de izquierda a derecha:

((λx.λy.x+y) 3) 4

Primero aplico el 3. Sustituyo x por 3 en el cuerpo:

((λx.λy.x+y) 3) 4
→ (λy.3+y) 4

Fíjate qué ha pasado: después del primer paso me queda una función que aún espera un y. Esa es la aplicación parcial — la base de cómo funcionan las funciones en Haskell.

Ahora aplico el 4. Sustituyo y por 4:

(λy.3+y) 4
→ 3+4
→ 7

Listo. La función completa se ha reducido a su forma final, 7. Esa forma final, la que ya no se puede reducir más, se llama forma normal.

Y eso es toda la maquinaria del lambda calculus. Sustituye. Sustituye otra vez. Sigue hasta que no puedas. Lo que queda es el resultado.

Variables ligadas y variables libres

Una distinción sutil pero importante. Cuando ves una variable en una expresión lambda, puede ser de dos tipos.

Mira esta:

λx.x+1

Aquí hay una variable, x, que aparece dos veces. Pero las dos apariciones cumplen roles distintos:

• La primera x —la que va después de la lambda— se está declarando como parámetro.
• La segunda x —la que va en el cuerpo— se está usando.

La x del cuerpo está ligada a la lambda. Como en cualquier lenguaje con scope: cuando en Python escribes def f(x): return x+1, la x del return se refiere al parámetro. Misma idea.

Ahora mira esta otra:

λx.x+y

Hay dos variables: x e y.

• x está ligada a la lambda, igual que antes.
• y aparece en el cuerpo pero no la declara ninguna lambda. Viene de fuera. Esa y se llama variable libre.

La función λx.x+y no es autocontenida — depende de un y que tiene que existir en algún sitio del contexto. Es como en Python si haces:

def f(x):
    return x + y

Esa función solo funciona si y está definida en algún sitio antes —variable global, scope superior, lo que sea—. Si no, error.

La regla para distinguirlas

Para cada variable que veas en el cuerpo de una expresión lambda, busca de dentro hacia fuera. Si te encuentras una lambda que la declara como parámetro, esa variable está ligada. Si llegas al principio de la expresión sin encontrarla, está libre.

Por qué importa

Por una razón muy práctica que veremos en la siguiente sección: puedes cambiar los nombres de las variables ligadas sin cambiar la función. Pero las libres no — son referencias al mundo exterior.

Alfa-equivalencia — el nombre del parámetro da igual

Estas dos lambdas son la misma función:

λx.x+1
λa.a+1

Y esta también:

λpepito.pepito+1

Las tres toman algo y le suman uno. El nombre que le pongas al parámetro es interno — desde fuera de la lambda no se ve. Cambiar el nombre del parámetro se llama alfa-conversión, y dos expresiones que se diferencian solo en eso son alfa-equivalentes.

Pero atención: esto solo vale para variables ligadas. Si renombras una variable libre, cambias la función, porque estás cambiando a qué te refieres de fuera. Estas dos NO son la misma función:

λx.x+y
λx.x+z

Aunque las dos sean "una función que toma x y le suma algo de fuera", ese "algo" es distinto en cada una. Si y vale 10 en el contexto y z vale 99, las dos funciones devuelven cosas distintas para el mismo x.

Resumen mental: nombres de parámetros son etiquetas internas, da igual cómo los llames. Nombres de variables libres apuntan a algo de fuera, así que importan.

El combinator K — la función que ignora

Un combinator es una lambda especial: una que no tiene variables libres. Es decir, una función autocontenida, que no depende de nada de fuera. Hay tres combinators famosos —~I~, K y ~S~— y casi todo lo demás se puede construir a partir de ellos.

Ya viste I, la identidad: λx.x. Devuelve lo que le metas.

El siguiente es K. Su definición:

λx.λy.x

Léela: "toma x, devuelve una función que toma y y devuelve… x". Fíjate bien: en el cuerpo solo aparece x. La y no aparece para nada. Esta función se carga su segundo argumento y devuelve el primero.

Vamos a reducirlo paso a paso. Aplico K a 5 y 7:

((λx.λy.x) 5) 7
→ (λy.5) 7        -- sustituyo x por 5
→ 5                -- sustituyo y por... bueno, y no aparece, así que
                   --   el resultado es 5 tal cual

El 7 desaparece. Como si nunca lo hubieras pasado.

Esto se llama el combinator K —de "Konstant", en alemán— y aparece en Haskell con el nombre const. Por eso const 5 7 te devuelve 5, ignorando el 7.

¿Para qué sirve esto? Parece una tontería pero aparece constantemente en código real. Por ejemplo, cuando quieres una lista del mismo elemento repetido:

map (const 0) [1, 2, 3, 4, 5]

Esa expresión dice: "para cada elemento de esa lista, ignóralo y devuelve 0". Resultado: [0, 0, 0, 0, 0]. Esa es la forma idiomática en Haskell de decir "olvídate de lo que había, mete esto en su lugar".

El combinator S — el duplicador

El tercer combinator famoso. Su definición:

λx.λy.λz.x z (y z)

Tres parámetros —~x~, y, z~— y un cuerpo que parece complicado: ~x z (y z). Leamos el cuerpo despacio porque es lo importante.

x z (y z) significa: "aplica x a dos argumentos. El primero es z. El segundo es el resultado de aplicar y a z".

Es decir: tanto x como y van a recibir z. La z se duplica. Y luego los resultados se combinan con x.

Esa es S en una frase: "coge tres cosas, pasa la tercera a las dos primeras, y luego junta los resultados con la primera".

Vamos a verlo con un ejemplo concreto. Aplico S usando:

• x = la suma, es decir, el operador +
• y = "multiplicar por dos", es decir, λn.n*2
• z = el número 3

Aplico S a estos tres:

((S (+)) (λn.n*2)) 3

Reduzco paso a paso sustituyendo en λx.λy.λz.x z (y z):

((S (+)) (λn.n*2)) 3
→ ((λy.λz.(+) z (y z)) (λn.n*2)) 3    -- sustituyo x por (+)
→ (λz.(+) z ((λn.n*2) z)) 3            -- sustituyo y por (λn.n*2)
→ (+) 3 ((λn.n*2) 3)                   -- sustituyo z por 3
→ (+) 3 (3*2)
→ (+) 3 6
→ 3 + 6
→ 9

Lo importante: el 3 se ha usado dos veces — una en (+) 3 ... y otra dentro de (λn.n*2) 3. Por eso S se llama el "duplicador". Coge el tercer argumento y lo reparte entre los dos primeros.

S es genuinamente difícil la primera vez. No te frustres si te toca releer la reducción dos veces — yo también la releí mil veces cuando la estudié. Lo importante por ahora no es dominar el mecanismo a fondo sino entender la idea: S es la herramienta que reparte un mismo argumento entre dos funciones distintas.

Aviso importante — te he hecho trampa pedagógica

Antes de seguir tengo que confesar algo. En las secciones anteriores he usado ejemplos del estilo "aplico S a (+) y (*2) y 3" para que veas lo que pasa con valores concretos. Eso es útil para visualizar, pero también es mentira a medias.

En lambda calculus puro —el original de Church de los años treinta— no existen los números. No existe el 3. No existe la suma. No existen los booleanos, las listas, los strings, nada. Solo existen lambdas. Solo funciones.

¿Y entonces cómo se hace aritmética sin números?

Se construyen los números con lambdas. Te lo enseñé en los ejercicios al final del post con los Church numerals. El número 3 en lambda calculus puro es exactamente:

3 = λf.λx.f (f (f x))

Una función que toma otra función f y un valor x, y aplica f tres veces a x. Eso es el 3 en lambda calculus. No es una metáfora ni una representación — es el número, no hay otro.

La suma también. La booleana true también —es λx.λy.x, idéntica al combinator K—. Todo, absolutamente todo, es función.

Cuando antes te dije "aplico S a (+)", lo que estaba haciendo era mezclar lambda calculus con la aritmética de toda la vida para que fuera digerible. En lambda calculus real, (+) tampoco existe — habría que construirlo como una lambda gigante que opera sobre Church numerals.

Eso te puede generar una duda muy razonable: si todo es función, ¿cómo sé en una expresión cualquiera qué papel hace cada cosa? Es la pregunta clave del lambda calculus y la enfrentamos en la siguiente sección.

Composición vs S — el familión

Antes de seguir con I = S K K, dejo aquí un puente para que conectes S con algo que ya te suena: la composición de funciones.

En Haskell la composición se escribe con punto:

(f . g) a = f (g a)

Aplica g a a, mete el resultado en f. La a aparece una sola vez — acaba dentro de g y no se vuelve a ver.

Esa composición en lambda calculus tiene nombre propio: es el combinator B, primo cercano de K y S:

B = λx.λy.λz.x (y z)

Tres parámetros, cuerpo x (y z). Pura composición.

Ahora compara con S:

S = λx.λy.λz.x z (y z)

¿Ves la diferencia? En B la z solo aparece dentro de y z. En S la z aparece dos veces: una como argumento de x directo, otra dentro de y z.

Es decir: S es composición con un giro. No solo encadena y → x. También le pasa la entrada original z a x como primer argumento.

B (composición): z → g → r              → f → final
                 (z se "pierde" en g, f solo ve el resultado)

S:               z → g → r
                 ↘___________________→ f(z, r) → final
                  (z también llega a f por su cuenta)

Por eso S se llama "el duplicador". Esa duplicación es lo que le da el poder extra sobre la composición. Con B y K puedes hacer muchas cosas pero no todas. Con S y K puedes hacer cualquier cosa. La diferencia es ese pequeño giro de "y la z también la ve la otra función".

Si esto te suena a poco — espera. Ese mismo patrón vuelve a aparecer en Haskell mucho más adelante. Cuando lleguemos al concepto Applicative en el capítulo 17 del libro, la función <*> aplicada al tipo de las funciones es literalmente S. La intuición que estás construyendo ahora —"la entrada se reparte entre dos cosas distintas"— vas a usarla en código real.

Pero entonces, ¿cómo sé qué es función y qué no?

Esta pregunta merece su propia sección porque es justa y profunda.

Si todo es función en lambda calculus puro, cuando ves una expresión como S K K x, ¿cómo sabes qué papel hace cada cosa? ¿Cómo sabes que K es función pero quizás x es un valor?

La respuesta tiene dos partes según en qué mundo estés.

En lambda calculus puro

No lo sabes. Y no hace falta saberlo. Todo es función. La única distinción que importa es la posición sintáctica.

Cuando escribes S K K x, la sintaxis se lee como "aplica S a K, luego eso a K, luego eso a x". Para que cada aplicación tenga sentido:

• S tiene que ser algo aplicable → lo es porque es una lambda.
• (S K) tiene que ser aplicable a K → lo es porque al aplicar S a algo, el resultado sigue siendo una lambda.
• ((S K) K) tiene que ser aplicable a x → sigue siéndolo.
• x no tiene que ser nada en particular. Puede ser otra lambda. Puede ser un Church numeral —que también es una lambda—. Puede ser cualquier cosa que la siguiente operación necesite que sea.

Lambda calculus no pregunta "qué tipo es esto". Solo aplica. Si en algún paso intentas aplicar algo que no se puede aplicar, te quedas atascado. Y atascarse, en lambda calculus, ya es una respuesta.

En Haskell

Aquí cambia todo. Haskell tiene tipos, y los tipos te chivan exactamente qué es cada cosa. Lo demuestro.

Si en GHCi escribes:

:t \f g a -> f a (g a)

GHCi te responde:

\f g a -> f a (g a) :: (t1 -> t2 -> t3) -> (t1 -> t2) -> t1 -> t3

Lee esa firma despacio:

• El primer argumento, f, tiene tipo (t1 -> t2 -> t3). Es decir, tiene que ser una función de dos argumentos — toma un t1, luego un t2, y devuelve un t3.
• El segundo argumento, g, tiene tipo (t1 -> t2). Tiene que ser una función de un argumento — toma un t1 y devuelve un t2.
• El tercer argumento, a, tiene tipo t1. Puede ser cualquier cosa — pero su tipo (t1) tiene que coincidir con lo que f y g esperan.
• El resultado tiene tipo t3.

GHCi ha deducido todo eso sin que tú escribieras ningún tipo. Solo mirando \f g a -> f a (g a), ha sacado quién es función, de cuántos argumentos, y qué encaja con qué.

A eso se le llama inferencia de tipos y es una de las características más bonitas de Haskell. El compilador hace de Sherlock Holmes con tu código: lee, deduce, y te dice quién es quién. Tú no declaras nada — él lo saca solo.

Resumen mental

Truco práctico para cuando empieces a escribir Haskell: cuando veas una expresión que no entiendes, dale :t delante en GHCi. Es tu lupa. El compilador es el mejor profesor de tipos que existe.

I igual a S K K — la demostración bonita

Acuérdate de los tres combinators: I es la identidad, K ignora su segundo argumento, S duplica el tercero entre los dos primeros.

Pues bien, a partir de K y S, puedes construir I.

Es decir: I = S K K. La identidad sale gratis si tienes los otros dos. Vamos a demostrarlo reduciendo S K K x y ver que sale x:

S K K x

Paso 1 — desplegamos S. La definición de S es S f g z = f z (g z).
         Aquí f=K, g=K, z=x. Entonces:
   → K x (K x)

Paso 2 — el primer K toma dos argumentos y devuelve el primero.
         Los argumentos de este K son x y (K x).
         Devuelve el primero: x.
   → x

Y ya está. S K K x = x para cualquier x. Es la identidad, construida con solo S y K. Mira lo demás que pueda decir: nada. Pura combinatoria.

Pero el resultado va mucho más lejos de lo que parece. Los matemáticos demostraron en los años treinta que con SOLO esos dos combinators —~S~ y ~K~— puedes expresar cualquier programa que se pueda escribir en cualquier lenguaje. Cualquiera. Sistemas operativos, navegadores, juegos, redes neuronales, todo reducible a árboles de S y K.

A esto se le llama la base SK y es uno de los resultados más bonitos de la teoría de la computación. Existen incluso lenguajes de programación serios construidos sobre esta idea —Unlambda, Lazy K—. Y los primeros compiladores de Haskell, en los años ochenta, traducían literalmente el código a árboles de S y K y los reducían. Esa técnica se llamaba graph reduction.

Es decir: lo que acabas de ver no es un truco. Es la base teórica sobre la que se construyó el lenguaje que estás aprendiendo.

Por qué importa todo esto

Voy a ser directo. Lo que acabas de aprender —lambdas, beta reducción, variables ligadas y libres, alfa-equivalencia, combinators— parece abstracto y desconectado del Haskell que querías aprender. No lo es.

Te enumero cuatro cosas que en Haskell vas a hacer la semana que viene y que no tienen sentido sin esto:

1. Funciones anónimas. Escribir \x -> x + 1 es escribir una lambda. La sintaxis cambia, el concepto es idéntico.

2. Currying y aplicación parcial. Cuando escribes suma 3 y eso te devuelve "una función que espera el segundo argumento", estás haciendo lo mismo que cuando reduces (λx.λy.x+y) 3 y te queda λy.3+y. Es lambda calculus puro con sintaxis Haskell.

3. Composición de funciones. El operador punto en Haskell —~f . g~— es esencialmente el combinator B —el primo de K y S que es ~λx.λy.λz.x (y z)~—. Cuando compones funciones estás haciendo reducciones lambda.

4. Pereza, mónadas, functors, applicative. Todo se construye sobre estos cimientos. Cuando lleguemos a las mónadas y te explique el operador >>=, vas a ver lambdas anidadas — exactamente como S — pero ahora con un significado más rico. Si tienes lambda calculus en la cabeza, las mónadas son la siguiente abstracción natural. Si no, son magia.

Por eso vale la pena pararse aquí. Por eso HPFP empieza así. Por eso yo no me lo voy a saltar contigo aunque pique las ganas.

Ejercicios

Esto no se queda en la cabeza por leerlo — se queda en la cabeza por ejercitarlo. Te dejo a continuación los ejercicios fundamentales del capítulo. Los primeros tres bloques —A, B y C— son a papel y boli. Lambda calculus puro sin Haskell.

Si quieres también los bloques avanzados —D con combinators implementados en Haskell, E con codificaciones de Church para booleanos y números— los tienes en el fichero EJERCICIOS.org del aula local. Aquí pongo los tres fundacionales para que cualquiera los pueda hacer mientras lee el post.

Bloque A — Beta reducción a mano

Reduce cada expresión hasta su forma normal. Escribe todos los pasos con la flecha →, no solo el resultado.

A.1 — calentamiento:

(λx.x + 7) 3

A.2 — currying:

((λx.λy.x - y) 10) 3

A.3 — lambda anidada que devuelve lambda:

((λx.λy.y) 99) 5

Pista: mira el cuerpo de la primera lambda. ¿En qué se transforma cuando sustituyes x por 99?

A.4 — orden de aplicación importa:

((λx.λy.x y) (λz.z+1)) 4

A.5 — cuando una lambda se aplica a otra lambda:

(λf.λx.f (f x)) (λn.n*2) 3

Pista: sustituye f primero —es λn.n*2~—, luego ~x —es 3~—. Cuidado con los paréntesis: ~f (f x) significa "aplicar f al resultado de aplicar f a x".

Bloque B — Variables ligadas vs libres

Para cada expresión, lista qué variables hay y di si son ligadas —declaradas por una lambda en la misma expresión— o libres —vienen de fuera—.

B.1 — λx.x + y

B.2 — λx.λy.x + y + z

B.3 — la sutil. (λx.x) (λy.y + x). ¿La x del segundo paréntesis es la misma que la del primero?

B.4 — shadowing. λx.λx.x. ¿Cuál es la x del cuerpo: la de la primera lambda o la de la segunda?

Bloque C — Alfa-equivalence

Para cada par, di si son alfa-equivalentes —la misma función con distintos nombres— o no.

C.1 — λx.x + 1 y λy.y + 1

C.2 — λx.x + y y λz.z + y

C.3 — la trampa de renombrar una libre. λx.x + y y λx.x + z

C.4 — capture-avoiding. ¿Puedo renombrar la x ligada de λx.x + y a λy.y + y?

Las soluciones

No están en este post a propósito. Están en el fichero EJERCICIOS.org del aula local, plegadas debajo de cada enunciado. La idea es que si me lees, lo intentes primero tú. Después me preguntas en sesión y vamos juntos a las que te hayan costado.

Cuando hayas terminado

No tengas prisa. Estos ejercicios no son trámite — son donde lambda calculus pasa de "lo entendí cuando lo leí" a "lo tengo en los dedos". La diferencia es lo que separa al que sabe Haskell del que usa Haskell.

Si te atascas en alguno, anótalo y tráelo a la siguiente sesión. Las dudas valen más que las soluciones — me dicen qué tengo que explicar mejor.

Y cuando lo tengas todo en limpio, pasamos al capítulo 2 con la cabeza tranquila. Ya verás que después de cap 1 hecho con calma, todo lo que venga después se entiende casi solo.

Sin prisa. Las funciones puras no tienen prisa.

— Haskell-Sensei, en aurin, 24 de mayo de 2026.