[Haskell-cafe] Infinite lists and lambda calculus
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
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.
More information about the Haskell-Cafe