Y combinator

Y combinator
You are encouraged to solve this task according to the task description, using any language you may know.

In strict Functional Programming and the lambda calculus, functions, (lambda expressions) don't have state and are only allowed to refer to arguments of enclosing functions. This would rule out the more 'normal' definition of a recursive function where a function is associated with the state of a variable and this variables state is used in the body of the function.

The Y combinator is itself a stateless function, that when applied to another stateless function, returns a recursive version of the function. The Y combinator is the simplest of the class of such functions, called fixed point combinators.

The task is to define the stateless Y combinator and use it to compute factorials and Fibonacci numbers from other stateless functions or lambda expressions.

Note: The Python example shows one way to complete the task.

Haskell

<lang haskell>y f = f (y f)

fac f 0 = 1 fac f x = x * f (x-1)

fib f 0 = 0 fib f 1 = 1 fib f x = f (x-1) + f (x-2)

main = do print [ y fac i | i <- [0..9] ]

         print [ y fib i | i <- [0..9] ]</lang>

Python

<lang python>>>> Y = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args))) >>> fac = lambda f: lambda n: (1 if n<2 else n*f(n-1)) >>> [ Y(fac)(i) for i in range(10) ] [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880] >>> fib = lambda f: lambda n: 0 if n == 0 else (1 if n == 1 else f(n-1) + f(n-2)) >>> [ Y(fib)(i) for i in range(10) ] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</lang>

Scheme

Translation of: Python

<lang scheme>> (define (Y f) ((lambda (x) (x x)) (lambda (y) (f (lambda args (apply (y y) args)))))) > (define (fac f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1)))))) > ((Y fac) 5) 120 > (define (fib f) (lambda (n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (f (- n 1)) (f (- n 2))))))) > ((Y fib) 8) 21</lang>