Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
The factorial function implemented in the lambda calculus
// In the lambda calculus, an expression must be one of the following:
// 1) function(x) { return expression; }
// 2) expression(expression)
// 3) x
// Pairs
const pair = function(x) {
return function(y) {
return function(f) {
return f(x)(y);
};
};
};
const first = function(p) {
return p(
function(x) {
return function(y) {
return x;
};
}
);
};
const second = function(p) {
return p(
function(x) {
return function(y) {
return y;
};
}
);
};
// Arithmetic on natural numbers
const zero = function(f) { return function(x) { return x; } };
const one = function(f) { return function(x) { return f(x); } };
const increment = function(x) {
return function(f) {
return function(y) {
return f(x(f)(y));
};
};
};
const decrement = function(x) {
return first(
x(
function(p) {
return pair(second(p))(increment(second(p)));
}
)(pair(zero)(zero))
);
};
const add = function(x) {
return function(y) {
return x(increment)(y);
};
};
const multiply = function(x) {
return function(y) {
return x(add(y))(zero);
}
};
// The "Z" combinator for looping
const z = function(f) {
return (
function(x) {
return function(z) {
return f(x(x));
};
}
)(
function(x) {
return function(z) {
return f(x(x));
};
}
);
};
// The identity function
const id = function(x) {
return x;
};
// And finally: the factorial function!
const factorial = z(
function(f) {
return function(x) {
return x(
function(y) {
return function(q) {
return multiply(x)(f(id)(decrement(x)));
};
}
)(
function(q) { return one; }
)(id);
};
}
)(id);
// Debugging
function print(y) {
console.log(y(function(x) { return x + 1; })(0));
}
const two = increment(one);
const four = add(two)(two);
const five = increment(four);
print(factorial(five)); // Prints 120
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.