Kata

(intro stolen from Azuaron)

Lambda Calculus

Lambda Calculus is a syntax for functional computing/mathematics. In Lambda Calculus, a function has one input, and one output. However, the input function can be another lambda function (which accepts another input), and this can somewhat simulate multiple inputs with some important differences; this is called "currying".

Some languages (e.g. Haskell) naturally use curried functions. Other languages (e.g. Javascript) must have currying forced upon them. The solution starts with the functions properly curried, and will need to remain that way.

Church Encodings

In mathematics, Church encoding is a means of representing data and operators in the lambda calculus. Church numerals are a representation of the natural numbers using lambda notation.
Terms that are usually considered primitive in other notations (such as integers, booleans, pairs and lists) are mapped to higher-order functions under Church encoding. This is an important concept of Lambda Calculus, so naturally we had to talk about Lambda Calculus.

The Task

Create a FACTORIAL function which has one parameter n, the number that we should calculate the factorial of.

Examples

FACTORIAL(ZERO)   =>  1
FACTORIAL(ONE)    =>  1
FACTORIAL(TWO)    =>  2
FACTORIAL(THREE)  =>  6
FACTORIAL(FOUR)   =>  24
FACTORIAL(FIVE)   =>  120

Syntax

This is Lambda Calculus, and so there are restrictions on the syntax allowed.

You can define constants in Lambda Calculus syntax only: variables, function expressions, and function calls. Declare your definitions with const. Function expressions must use fat arrow syntax ( => ). Functions can have zero or one argument. You can define and use helper constants. Empty applications are allowed. Recursion is not restricted.

Some examples of valid syntax:

const pair = a => b => c => c(a)(b)
const zero = f => x => x
const cons = pair

Some examples of invalid syntax:

one = f => x => f(x);                // semicolons (;) are not allowed
function head(l) { return l(true) }  // functions must use fat arrow notation
fold = f => x => l => l.reduce(f, x) // only variables, functions and applications are allowed;
                                     // property accessors (.), or functions taking multiple arguments, are not allowed

Preloaded

You will be given the following definitions:

ZERO  = s => z => z
ONE   = s => z => s(z)
TWO   = s => z => s(s(z))
THREE = s => z => s(s(s(z)))
FOUR  = s => z => s(s(s(s(z))))
FIVE  = s => z => s(s(s(s(s(z)))))
SUCC  = n => s => z => s(n(s)(z))
PRED  = n => n-1                       //  actually defined differently :]
TRUE  = t => f => t
FALSE = t => f => f
IS_ZERO = n => n ( _ => FALSE) (TRUE)  //  returns a Church Boolean

zero  = \ s z . z
one   = \ s z . s z
two   = \ s z . s (s z)
three = \ s z . s (s (s z))
four  = \ s z . s (s (s (s z)))
five  = \ s z . s (s (s (s (s z))))
succ  = \ n . \ s z . s (n s z)
pred  = \ n . n-1                     #  actually defined differently :]
True  = \ true _false . true
False = \ _true false . false
is-zero = \ n . n (\ _ . False) True  #  returns a Church Boolean

data Term = Lambda { apply :: Term -> Term }

infixl 1 `apply`

lambda :: (Term -> Term) -> Term
lambda = Lambda

zero,one,two,three,four,five,succ,pred,false,true,isZero :: Term
zero  = lambda $ \ s -> lambda $ \ z -> z -- = false
one   = lambda $ \ s -> lambda $ \ z -> s `apply` z
two   = lambda $ \ s -> lambda $ \ z -> s `apply` (s `apply` z)
three = lambda $ \ s -> lambda $ \ z -> s `apply` (s `apply` (s `apply` z))
four  = lambda $ \ s -> lambda $ \ z -> s `apply` (s `apply` (s `apply` (s `apply` z)))
five  = lambda $ \ s -> lambda $ \ z -> s `apply` (s `apply` (s `apply` (s `apply` (s `apply` z))))
succ  = lambda $ \ n -> lambda $ \ s -> lambda $ \ z -> s `apply` (n `apply` s `apply` z)
pred  = lambda $ \ n -> n - 1                                            --  actually defined differently :]
false = lambda $ \ t -> lambda $ \ f -> f
true  = lambda $ \ t -> lambda $ \ f -> t
isZero = lambda $ \ n -> n `apply` (lambda $ \ _ -> false) `apply` true  --  returns a Church Boolean

Notes

JavaScript uses strict evaluation. You may have to use thunks to apply laziness to predicates like IS_ZERO.

Help

Wikipedia: Lambda Calculus

Wikipedia: Church Encoding