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

[Miguel Mitrofanov]

Wow. Now you've showed it to me, it seems pretty obvious. That's what  
I like about math.

On 21 Jun 2009, at 21:56, Bertram Felgenhauer wrote:

> 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.
>
> Consider
>
> (\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.
>
> Bertram
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe