I have a few drafts of this post sitting around but they all miss something or at least I can’t shake the feeling that they miss something. Instead of trying to articulate it I’m going to defer to older and wiser people. Continue reading

factorial without recursion or loops

Our destination is the applicative form of the y-combinator and our starting point is the incomplete form of the factorial function. We will get to our destination by lifting sub-expressions with lambdas.

Starting Point

Here’s a recursive definition of factorial

and here’s an incomplete definition of factorial

Notice that in the incomplete definition of factorial we don’t mention incomplete within the body of the function. There is something else in that definition that should have you scratching your head and it is the expression g[g]. I don’t know a good way of motivating how that expression comes about. The intuition is that g is special somehow and we need to keep a copy of it around. In the absence of variables the only way to keep a copy of something is to make it a parameter so I’m anticipating keeping a copy of something around. Can you guess what I’m trying to keep a copy of? Continue reading