the Lambda Calculus is often taught or presented in ways that are kind of weird and mysterious, with things like the Y combinator as some magical "look at this weird magic! i'm a wizard!" kind of thing
so i want to demystify the Y combinator
Replies:
4
lets start by looking at the problem. lets suppose we have some flavor of lambda calculus. im going to use something that looks like haskell. and we define factorial like so:
fac = \n -> if n == 0 then 1 else n * fac (n - 1)
this is a perfectly fine definition of factorial, but it relies on having a primitive notion of named functions. what if we want to avoid that. can we some how come up with a mechanism for getting the same effect?
maybe!
but only maybe. we have to do some calculations
lets observe, first, that we can factor out the recursive occurrence like so:
fac = (\r -> \n -> if n == 0 then 1 else n * r (n - 1)) fac
and now let's abbreviate like so:
F := \r -> \n -> if n == 0 then 1 else n * r (n - 1)
this is just an abbreviation for us while writing, it's not a part of the program
