Un breve repaso sobre Cálculo λ

En Haskell tenemos una manera análoga de trabajar a como lo hacemos en el cálculo $\lambda$. Por ejemplo, si escribimos la abstracción $\lambda x.x+x$, esto en Haskell se vería de la siguiente manera:

\x -> x + x

Usamos una flecha -> en lugar de un punto para denotar el cuerpo de la función, y una diagonal invertida \ porque visualmente se asemeja a una $\lambda$.

Para la aplicación, el proceso se ve así:

ghci> (\x -> x + x) 6
12

Su reducción análoga en el cálculo $\lambda$ puro sería: $(\lambda x.x+x)6=(x+x)[x:=6]=6+6=12$ Ahora, quizá me digan: ¡Estás haciendo trampa! Estás usando la suma y los números de Haskell. Y tienen razón, así que les mostraré los numerales de Church desde cero.

Número	Cálculo $\lambda$
0	$\lambda f.\lambda x.x$
1	$\lambda f.\lambda x.fx$
2	$\lambda f.\lambda x.f(fx)$
3	$\lambda f.\lambda x.f(f(fx))$

let cero = \f -> \x -> x
let uno  = \f -> \x -> f x
let dos  = \f -> \x -> f (f x)
let tres = \f -> \x -> f (f (f x))
 
let churchToInt = \c -> c (+1) 0
-- La suma en el cálculo lambda
let sumar = \m -> \n -> \f -> \x -> m f (n f x) 

$sumar\equiv \lambda m.\lambda n.\lambda f.\lambda x.mf(nfx)$

ghci> churchToInt (sumar dos tres)
5