[Haskell-cafe] Infinite lists and lambda calculus

Paul Hudak paul.hudak at yale.edu
Fri Nov 18 20:42:25 EST 2005


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


More information about the Haskell-Cafe mailing list