[Haskell-cafe] Infinite lists and lambda calculus

[Paul Hudak]

Cale Gibbard wrote:
>>Y = (\f. (\x. f (x x)) (\x. f (x x)))
> 
> In a sense, the real definition of Y is Y f = f (Y f), this lambda
> term just happens to have that property, but such functions aren't
> rare.

Actually no, the "real" definition is the top one, because the other one 
isn't even a valid lambda term, since it's recursive!  There is no such 
thing as recursion in the pure lambda calculus.

Of course, there are many valid definitions of Y, as you point out, both 
recursive and non-recursive.  But I do believe that the first one above 
is the most concise non-recursive definition.

   -Paul