[Haskell-cafe] Slightly off-topic: Lambda calculus

Bertram Felgenhauer bertram.felgenhauer at googlemail.com
Sun Jun 21 13:56:00 EDT 2009

Miguel Mitrofanov wrote:
> Correction: I think that one can find an expression that causes name 
> clashes anyway, I'm just not certain that there is one that would clash 
> independent of whichever order you choose.

Yes there is.


 (\f g -> f (f (f (f (f (f g)))))) (\l a b -> l (b a)) (\x -> x)

which has 6 variables in total. This reduces to the normal form

 \a b c d e f g -> g (f (e (d (c (b a)))))

which requires 7 variables. So without alpha-conversion at least one of
the original 6 variables will clash with itself.


More information about the Haskell-Cafe mailing list