# 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 rules out the usual definition of a recursive function wherein a function is associated with the state of a variable and this variable's 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.

## AppleScript

AppleScript is not terribly "functional" friendly. However, it is capable enough to support the Y combinator.

AppleScript does not have anonymous functions, but it does have anonymous objects. The code below implements the latter with the former (using a handler (i.e. function) named 'funcall' in each anonymous object).

Unfortunately, an anonymous object can only be created in its own statement ('script'...'end script' can not be in an expression). Thus, we have to apply Y to the automatic 'result' variable that holds the value of the previous statement.

The identifier used for Y uses "pipe quoting" to make it obviously distinct from the y used inside the definition. <lang AppleScript>to |Y|(f)

``` script x
to funcall(y)
script
to funcall(arg)
y's funcall(y)'s funcall(arg)
end funcall
end script
f's funcall(result)
end funcall
end script
x's funcall(x)
```

end |Y|

script

``` to funcall(f)
script
to funcall(n)
if n = 0 then return 1
n * (f's funcall(n - 1))
end funcall
end script
end funcall
```

end script set fact to |Y|(result)

script

``` to funcall(f)
script
to funcall(n)
if n = 0 then return 0
if n = 1 then return 1
(f's funcall(n - 2)) + (f's funcall(n - 1))
end funcall
end script
end funcall
```

end script set fib to |Y|(result)

set facts to {} repeat with i from 0 to 11

``` set end of facts to fact's funcall(i)
```

end repeat

set fibs to {} repeat with i from 0 to 20

``` set end of fibs to fib's funcall(i)
```

end repeat

{facts:facts, fibs:fibs} (* {facts:{1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800},

```fibs:{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765}}
```
• )</lang>

## C#

<lang csharp>using System;

namespace YCombinator {

```   public class Program
{
private delegate Func<int, int> Recursive(Recursive recursive);
```
```       public static void Main()
{
Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>> Y =
f => ((Recursive)(g => f(x => g(g)(x))))((Recursive)(g => f(x => g(g)(x))));
```
```           Func<Func<int, int>, Func<int, int>> fac =
f => x => x < 1 ? 1 : x * f(x - 1);
```
```           Func<Func<int, int>, Func<int, int>> fib =
f => x => x < 2 ? x : f(x - 1) + f(x - 2);
```
```           Console.WriteLine((Y(fac))(6));
```
```           Console.WriteLine((Y(fib))(6));
}
}
```

}</lang> Output: <lang>720 8</lang>

## Clojure

<lang lisp>(defn Y [f]

``` ((fn [x] (x x))
(fn [x]
(f (fn [& args]
(apply (x x) args))))))
```

(def fac

```    (fn [f]
(fn [n]
(if (zero? n) 1 (* n (f (dec n)))))))
```

(def fib

```    (fn [f]
(fn [n]
(condp = n
0 0
1 1
(+ (f (dec n))
(f (dec (dec n))))))))</lang>
```

Sample output:

```user> ((Y fac) 10)
3628800
user> ((Y fib) 10)
55```

`Y` can be written slightly more concisely via syntax sugar:

<lang lisp>(defn Y [f]

``` (#(% %) #(f (fn [& args] (apply (% %) args)))))</lang>
```

## Common Lisp

<lang lisp>(defun Y (f)

``` ((lambda (x) (funcall x x))
(lambda (y)
(funcall f (lambda (&rest args)
```

(apply (funcall y y) args))))))

(defun fac (f)

``` (lambda (n)
(if (zerop n)
```

1 (* n (funcall f (1- n))))))

(defun fib (f)

``` (lambda (n)
(case n
(0 0)
(1 1)
(otherwise (+ (funcall f (- n 1))
```

(funcall f (- n 2)))))))

CL-USER> (loop for i from 1 to 10 collect (list i (funcall (Y #'fac) i) (funcall (Y #'fib) i)))
((1 1 1) (2 2 1) (3 6 2) (4 24 3) (5 120 5) (6 720 8) (7 5040 13)
(8 40320 21) (9 362880 34) (10 3628800 55))</lang>

## D

This is D 2.0 code.

It seems that though D is statically typed language, it is possible to make stateless Ycombinator.

If you look close enough, the definition of Ycomb is almost exactly the same as in Python version, but with types added.

The simple and proper way to do it looks like this:

<lang D>import std.stdio;

// helper aliases, just to make code shorter // and easier to read alias void delegate() DelVoid; alias ulong delegate(ulong) DelClassic;

DelClassic Ycomb(DelClassic delegate(DelClassic) f) {

```   return (DelClassic delegate(DelVoid) x) {
return x (cast(DelVoid)x);
}(
(DelVoid y) {
return f( (ulong args) {
return (cast(DelClassic)(cast(DelVoid delegate(DelVoid))y)(y))(args);
});
}
);
```

}

void main() {

```   DelClassic almostFac(DelClassic f) {
return delegate ulong(ulong n) {
return (n == 0 || n == 1) ? 1Lu : n * f(n-1);
};
};
DelClassic almostFib(DelClassic f) {
return delegate ulong(ulong n) {
return (n == 0 || n == 1) ? n : f(n-2) + f(n-1);
};
}
```
```   auto fac = Ycomb(&almostFac);
foreach (i; 1..15) writef(fac(i), ", "); writefln("");
```
```   auto fib = Ycomb(&almostFib);
foreach (i; 1..15) writef(fib(i), ", "); writefln("");
```

}</lang>

However above code can be templated to make it even more generic:

<lang D>import std.stdio, std.traits, std.algorithm, std.range, std.array;

ReturnType!(F) Y(F)(F f) { alias void delegate() DG; // just a shorthand alias ReturnType!(ParameterTypeTuple!(F)) Ret; alias ParameterTypeTuple!(ParameterTypeTuple!(F)) Params;

return (Ret delegate(Params) delegate(DG) x) { return x(cast(DG)x); }( (DG y) { return f((Params args) { return (cast(Ret delegate(Params))(cast(DG delegate(DG))y)(y))(args); }); } ); }

void main() { auto fac = Y((ulong delegate(ulong) self) { return (ulong n) { return 0 == n ? 1 : n*self(n-1); }; });

auto fib = Y((ulong delegate(ulong) self) { return (ulong n) { return n <= 1 ? n : self(n-1) + self(n-2); }; });

writeln("fac: ", array(map!fac(iota(0, 10)))); writeln("fib: ", array(map!fib(iota(0, 10)))); }</lang>

The above code works with DMD 2.031, but unfortunately not in D1, which doesn't have full closures. In D1, it's necessary to manually fix some variables from the surrounding scopes of the closures above, e.g. by using currying. The following might still be considered a stateless Y combinator, as the additional currying is just what any other language's compiler would do behind the scenes. The following works with DMD 1.045 + Tango:

<lang D>import tango.io.Stdout, tango.core.Traits;

ReturnTypeOf!(F) delegate(ParameterTupleOf!(F)[1..\$]) curry(F, Arg)(F f, Arg arg) { alias ParameterTupleOf!(F) Params; alias ReturnTypeOf!(F) Ret;

struct Context { Params[0] arg; F f; Ret call(Params[1..\$] p) { return f(arg, p); } }

auto ctx = new Context; ctx.arg = arg; ctx.f = f; return &ctx.call; }

ReturnTypeOf!(F) Y(F)(F f_) { alias void delegate() DG; // just a shorthand alias ReturnTypeOf!(ParameterTupleOf!(F)[0]) Ret; alias ParameterTupleOf!(ParameterTupleOf!(F)[0]) Params_;

// workaround for a bug in the compiler static if (1 == Params_.length) { alias Params_[0] Params; } else { alias Params_ Params; }

return (Ret delegate(Params) delegate(DG, F) x) { return x(cast(DG)x, f_); }( (DG y, F f) { return f(curry(curry((DG y, F f, Params args) { return (cast(Ret delegate(Params))(cast(DG delegate(DG, F))y)(y, f))(args); }, y), f)); } ); }

void main() { auto fac = Y((ulong delegate(ulong) self) { return curry((typeof(self) self, ulong n) { return 0 == n ? 1 : n*self(n-1); }, self); });

auto fib = Y((ulong delegate(ulong) self) { return curry((typeof(self) self, ulong n) { return n <= 1 ? n : self(n-1) + self(n-2); }, self); });

for (int i = 0; i < 10; ++i) { Stdout(fac(i))(' '); } Stdout.newline;

for (int i = 0; i < 10; ++i) { Stdout(fib(i))(' '); } Stdout.newline; }</lang>

## E

Translation of: Python

<lang e>def y := fn f { fn x { x(x) }(fn y { f(fn a { y(y)(a) }) }) } def fac := fn f { fn n { if (n<2) {1} else { n*f(n-1) } }} def fib := fn f { fn n { if (n == 0) {0} else if (n == 1) {1} else { f(n-1) + f(n-2) } }}</lang>

<lang e>? pragma.enable("accumulator") ? accum [] for i in 0..!10 { _.with(y(fac)(i)) } [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

? accum [] for i in 0..!10 { _.with(y(fib)(i)) } [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</lang>

## Erlang

<lang erlang>Y = fun(M) -> (fun(X) -> X(X) end)(fun (F) -> M(fun(A) -> (F(F))(A) end) end) end.

Fac = fun (F) ->

```         fun (0) -> 1;
(N) -> N * F(N-1)
end
end.
```

Fib = fun(F) ->

```         fun(0) -> 0;
(1) -> 1;
(N) -> F(N-1) + F(N-2)
end
end.
```

(Y(Fac))(5). %% 120 (Y(Fib))(8). %% 21</lang>

## F#

<lang fsharp>type 'a mu = Roll of ('a mu -> 'a)

let unroll (Roll x) = x //val unroll : 'a mu -> 'a

let fix f = (fun x a -> f (unroll x x) a) (Roll (fun x a -> f (unroll x x) a)) //val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>

let fac f = function

```   0 -> 1
| n -> n * f (n-1)
```

//val fac : (int -> int) -> int -> int = <fun>

let fib f = function

```   0 -> 0
| 1 -> 1
| n -> f (n-1) + f (n-2)
```

//val fib : (int -> int) -> int -> int = <fun>

fix fac 5;; // val it : int = 120

fix fib 8;; // val it : int = 21</lang>

## Factor

In rosettacode/Y.factor <lang factor>USING: fry kernel math ; IN: rosettacode.Y

Y ( quot -- quot )
```   '[ [ dup call call ] curry _ call ] dup call( x -- x )  ;
```
almost-fac ( quot -- quot )
```   '[ dup zero? [ drop 1 ] [ dup 1 - _ call * ] if ] ;
```
almost-fib ( quot -- quot )
```   '[ dup 2 >= [ 1 2 [ - _ call ] bi-curry@ bi + ] when ] ;</lang>
```

In rosettacode/Y-tests.factor <lang factor>USING: kernel tools.test rosettacode.Y ; IN: rosettacode.Y.tests

[ 120 ] [ 5 [ almost-fac ] Y call ] unit-test [ 8 ] [ 6 [ almost-fib ] Y call ] unit-test</lang> running the tests : <lang> ( scratchpad - auto ) "rosettacode.Y" test Loading resource:work/rosettacode/Y/Y-tests.factor Unit Test: { [ 120 ] [ 5 [ almost-fac ] Y call ] } Unit Test: { [ 8 ] [ 6 [ almost-fib ] Y call ] }</lang>

## Genyris

Translation of: Scheme

<lang genyris>def fac (f)

```   function (n)
if (equal? n 0) 1
* n (f (- n 1))
```

def fib (f)

``` function (n)
cond
(equal? n 0) 0
(equal? n 1) 1
else (+ (f (- n 1)) (f (- n 2)))
```

def Y (f)

``` (function (x) (x x))
function (y)
f
function (&rest args) (apply (y y) args)
```

assertEqual ((Y fac) 5) 120 assertEqual ((Y fib) 8) 21</lang>

## Groovy

Here is the simplest (unary) form of applicative order Y:

<lang groovy>def Y = { le -> ({ f -> f(f) })({ f -> le { x -> f(f)(x) } }) }

def factorial = Y { fac ->

```   { n -> n <= 2 ? n : n * fac(n - 1) }
```

}

assert 2432902008176640000 == factorial(20G)

def fib = Y { fibStar ->

```   { n -> n <= 1 ? n : fibStar(n - 1) + fibStar(n - 2) }
```

}

assert fib(10) == 55</lang>

This version was translated from the one in The Little Schemer by Friedman and Felleisen. The use of the variable name le is due to the fact that the authors derive Y from an ordinary recursive length function.

A variadic version of Y in Groovy looks like this:

<lang groovy>def Y = { le -> ({ f -> f(f) })({ f -> le { Object[] args -> f(f)(*args) } }) }

def mul = Y { mulStar -> { a, b -> a ? b + mulStar(a - 1, b) : 0 } }

1.upto(10) {

```   assert mul(it, 10) == it * 10
```

}</lang>

The obvious definition of the Y combinator in Haskell canot be used because it contains an infinite recursive type (`a = a -> b`). Defining a data type (Mu) allows this recursion to be broken.

<lang haskell>newtype Mu a = Roll { unroll :: Mu a -> a }

fix :: (a -> a) -> a fix = \f -> (\x -> f (unroll x x)) \$ Roll (\x -> f (unroll x x))

fac :: Integer -> Integer fac = fix \$ \f n -> if (n <= 0) then 1 else n * f (n-1)

fibs :: [Integer] fibs = fix \$ \fbs -> 0 : 1 : fix zipP fbs (tail fbs)

``` where zipP f (x:xs) (y:ys) = x+y : f xs ys

```

main = do

``` print \$ map fac [1 .. 20]
print \$ take 20 fibs</lang>
```

The usual version using recursion, disallowed by the task:

<lang haskell>fix :: (a -> a) -> a fix f = f (fix f)

fac :: Integer -> Integer fac' f n | n <= 0 = 1

```        | otherwise = n * f (n-1)
```

fac = fix fac'

-- a simple but wasteful exponential time definition: fib :: Integer -> Integer fib' f 0 = 0 fib' f 1 = 1 fib' f n = f (n-1) + f (n-2) fib = fix fib'

-- Or for far more efficiency, compute a lazy infinite list. This is -- a Y-combinator version of: fibs = 0:1:zipWith (+) fibs (tail fibs) fibs :: [Integer] fibs' a = 0:1:(fix zipP a (tail a))

```   where
zipP f (x:xs) (y:ys) = x+y : f xs ys
```

fibs = fix fibs'

-- This code shows how the functions can be used: main = do

``` print \$ map fac [1 .. 20]
print \$ map fib [0 .. 19]
print \$ take 20 fibs</lang>
```

## J

In J, functions cannot take functions of the same type as arguments. In other words, verbs cannot take verbs and adverbs or conjunctions cannot take adverbs or conjunctions. However, the Y combinator can be implemented indirectly using, for example, the linear representations of verbs: <lang j>Y=. ((((&>)/)(1 : '(5!:5)<x'))(&([ 128!:2 ,&<)))f.</lang> The factorial and Fibonacci examples: <lang j> u=. [ NB. Function (left)

```  n=. ] NB. Argument (right)
sr=. [ 128!:2 ,&< NB. Self referring

fac=. (1:`(n * u sr n - 1:)) @. (0: < n)
fac f. Y 10
```

3628800

```  Fib=. ((u sr n - 2:) + u sr n - 1:) ^: (1: < n)
Fib f. Y 10
```

55</lang> The functions' stateless codings are shown next: <lang j> fac f. Y NB. Showing the stateless recursive factorial function... '1:`(] * [ ([ 128!:2 ,&<) ] - 1:)@.(0: < ])&>/'&([ 128!:2 ,&<)

```  fac f.   NB. Showing the stateless factorial step...
```

1:`(] * [ ([ 128!:2 ,&<) ] - 1:)@.(0: < ])

```  Fib f. Y NB. Showing the stateless recursive Fibonacci function...
```

'(([ ([ 128!:2 ,&<) ] - 2:) + [ ([ 128!:2 ,&<) ] - 1:)^:(1: < ])&>/'&([ 128!:2 ,&<)

```  Fib f.   NB. Showing the stateless Fibonacci step...
```

(([ ([ 128!:2 ,&<) ] - 2:) + [ ([ 128!:2 ,&<) ] - 1:)^:(1: < ])</lang> A structured derivation of Y follows: <lang j>sr=. [ 128!:2 ,&< NB. Self referring lw=. '(5!:5)<x' (1 :) NB. Linear representation of a word Y=. (&>)/lw(&sr) f. Y=. 'Y'f. NB. Fixing it</lang>

## Joy

<lang joy>DEFINE y == [dup cons] swap concat dup cons i;

```    fac == [ [pop null] [pop succ] [[dup pred] dip i *] ifte ] y.</lang>
```

## Lua

<lang lua>Y = function (f)

```  return function(...)
return (function(x) return x(x) end)(function(x) return f(function(y) return x(x)(y) end) end)(...)
end
```

end </lang>

Usage:

<lang lua>almostfactorial = function(f) return function(n) return n > 0 and n * f(n-1) or 1 end end almostfibs = function(f) return function(n) return n < 2 and n or f(n-1) + f(n-2) end end factorial, fibs = Y(almostfactorial), Y(almostfibs) print(factorial(7))</lang>

## OCaml

The Y-combinator over functions may be written directly in OCaml provided rectypes are enabled: <lang ocaml>let fix f g = (fun x a -> f (x x) a) (fun x a -> f (x x) a) g</lang> Polymorphic variants are the simplest workaround in the absence of rectypes: <lang ocaml>let fix f = (fun (`X x) -> f(x (`X x))) (`X(fun (`X x) y -> f(x (`X x)) y));;</lang> Otherwise, an ordinary variant can be defined and used: <lang ocaml>type 'a mu = Roll of ('a mu -> 'a);;

let unroll (Roll x) = x;;

let fix f = (fun x a -> f (unroll x x) a) (Roll (fun x a -> f (unroll x x) a));;

let fac f = function

```   0 -> 1
| n -> n * f (n-1)
```

let fib f = function

```   0 -> 0
| 1 -> 1
| n -> f (n-1) + f (n-2)
```

(* val unroll : 'a mu -> 'a mu -> 'a = <fun> val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun> val fac : (int -> int) -> int -> int = <fun> val fib : (int -> int) -> int -> int = <fun> *)

fix fac 5;; (* - : int = 120 *)

fix fib 8;; (* - : int = 21 *)</lang>

The usual version using recursion, disallowed by the task:

<lang ocaml>let rec fix f x = f (fix f) x;;</lang>

## Oz

<lang oz>declare

``` Y = fun {\$ F}
{fun {\$ X} {X X} end
fun {\$ X} {F fun {\$ Z} {{X X} Z} end} end}
end
```
``` Fac = {Y fun {\$ F}
fun {\$ N}
if N == 0 then 1 else N*{F N-1} end
end
end}
```
``` Fib = {Y fun {\$ F}
fun {\$ N}
case N of 0 then 0
[] 1 then 1
else {F N-1} + {F N-2}
end
end
end}
```

in

``` {Show {Fac 5}}
{Show {Fib 8}}</lang>
```

## Perl

<lang perl>my \$Y = sub { my (\$f) = @_; sub {my (\$x) = @_; \$x->(\$x)}->(sub {my (\$y) = @_; \$f->(sub {\$y->(\$y)->(@_)})})}; my \$fac = sub {my (\$f) = @_; sub {my (\$n) = @_; \$n < 2 ? 1 : \$n * \$f->(\$n-1)}}; print join(' ', map {\$Y->(\$fac)->(\$_)} 0..9), "\n"; my \$fib = sub {my (\$f) = @_; sub {my (\$n) = @_; \$n == 0 ? 0 : \$n == 1 ? 1 : \$f->(\$n-1) + \$f->(\$n-2)}}; print join(' ', map {\$Y->(\$fib)->(\$_)} 0..9), "\n";</lang>

## Perl 6

Works with: Rakudo version #22 "Thousand Oaks"

<lang perl6>sub Y (\$f) { { .(\$_) }( -> \$y { \$f({ \$y(\$y)(\$^arg) }) } ) } sub fac (\$f) { sub (\$n) { \$n < 2 ?? 1 !! \$n * \$f(\$n - 1) } } say map(Y(&fac), ^10).perl; sub fib (\$f) { sub (\$n) { \$n < 2 ?? \$n !! \$f(\$n - 1) + \$f(\$n - 2) } } say map(Y(&fib), ^10).perl;</lang>

Note that Perl 6 doesn't actually need a Y combinator because you can name anonymous functions from the inside:

Works with: Pugs

(Currently broken under Rakudo 2010.08) <lang perl6>say .(10) given sub (Int \$x) { \$x < 2 ?? 1 !! \$x * &?ROUTINE(\$x - 1); }</lang>

## PicoLisp

<lang PicoLisp>(de Y (F)

```  (let X (curry (F) (Y) (F (curry (Y) @ (pass (Y Y)))))
(X X) ) )</lang>
```

### Factorial

<lang PicoLisp># Factorial (de fact (F)

```  (curry (F) (N)
(if (=0 N)
1
(* N (F (dec N))) ) ) )
```
((Y fact) 6)

-> 720</lang>

### Fibonacci sequence

<lang PicoLisp># Fibonacci (de fibo (F)

```  (curry (F) (N)
(if (> 2 N)
1
(+ (F (dec N)) (F (- N 2))) ) ) )
```
((Y fibo) 22)

-> 28657</lang>

### Ackermann function

<lang PicoLisp># Ackermann (de ack (F)

```  (curry (F) (X Y)
(cond
((=0 X) (inc Y))
((=0 Y) (F (dec X) 1))
(T (F (dec X) (F X (dec Y)))) ) ) )
```
((Y ack) 3 4)

-> 125</lang>

## Pop11

<lang pop11> define Y(f);

```   procedure (x); x(x) endprocedure(
procedure (y);
f(procedure(z); (y(y))(z) endprocedure)
endprocedure
)
```

enddefine;

define fac(h);

```   procedure (n);
if n = 0 then 1 else n * h(n - 1) endif
endprocedure
```

enddefine;

define fib(h);

```   procedure (n);
if n < 2 then 1 else h(n - 1) + h(n - 2) endif
endprocedure
```

enddefine;

Y(fac)(5) => Y(fib)(5) => </lang>

Output:<lang>

• 120
• 8

</lang>

## PowerShell

Translation of: Python

<lang PowerShell>\$fac = {

```   	param([ScriptBlock] \$x)
invoke-expression @"
{
param([int] `\$n)
if (`\$n -le 0) {1}
else {`\$n * `\$({\$x}.Invoke(`\$n - 1))}
}
```

"@

```   }

```

\$fib = { param([ScriptBlock] \$f) invoke-expression @" { param([int] `\$n) switch (`\$n)

```       {
0 {1}
1 {1}
default {`\$({\$f}.Invoke(`\$n-1))+`\$({\$f}.Invoke(`\$n-2))}
}
```

} "@ }

\$Y = {

```   param([ScriptBlock] \$f)
invoke-expression @"
{
param([ScriptBlock] `\$x)
{\$f}.Invoke(`\$(invoke-expression @`"
{
param(```\$z)
```\$({`\$x}.Invoke({`\$x})).Invoke(```\$z)
}
```

`"@))

```   }.Invoke({
param([ScriptBlock] `\$x)
{\$f}.Invoke(`\$(invoke-expression @`"
{
param(```\$z)
```\$({`\$x}.Invoke({`\$x})).Invoke(```\$z)
}
```

`"@))

```   })[0]
```

"@ }

\$Y.Invoke(\$fac)[0].Invoke(5)

\$Y.Invoke(\$fib)[0].Invoke(5)</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>

## R

<lang R>Y <- function(f) {

``` (function(x) { (x)(x) })( function(y) { f( (function(a) {y(y)})(a) ) } )
```

}</lang>

<lang R>fac <- function(f) {

``` function(n) {
if (n<2)
1
else
n*f(n-1)
}
```

}

fib <- function(f) {

``` function(n) {
if (n <= 1)
n
else
f(n-1) + f(n-2)
}
```

}</lang>

<lang R>for(i in 1:9) print(Y(fac)(i)) for(i in 1:9) print(Y(fib)(i))</lang>

## REBOL

`Y: closure [g] [do func [f] [f :f] closure [f] [g func [x] [do f :f :x]]]`
usage example
```fact*: closure [h] [func [n] [either n <= 1 [1] [n * h n - 1]]]
fact: Y :fact*```

## REXX

<lang rexx> /*REXX program to implement Y combinator. */

numeric digits 20 parse arg Y say 'fib' say Y(fib (50)) /*Fibonacci series.*/ say 'fib' say Y(fib (12 11 10 9 8 7 6 5 4 3 2 1 0)) /*Fibonacci series.*/ say 'fact' say Y(fact (5)) /*single factorial.*/ say 'Dfact' say Y(fact (0 1 2 3 4 5 6 7 8 9 10 11)) /*single factorial.*/ say 'Dfact' say Y(dfact (4 5 6 7 8 9 10 11 12 13)) /*double factorial.*/ say 'Tfact' say Y(tfact (4 5 6 7 8 9 10 11 12 13)) /*triple factorial.*/ say 'Qfact' say Y(qfact (4 5 6 7 8 40)) /*quadruple factorial.*/ say 'length' say Y(length (when for to where whenceforth)) /*lengths*/ say 'reverse' say Y(reverse (23 678 1007 45 mas I ma)) /*reverses*/ say 'trunc' say Y(trunc (-7.0005 12 3.14159 6.4 78.999)) /*truncs*/ exit

```   Y: lambda=;arg Y _;do j=1 for words(_);interpret ,
'lambda=lambda' Y'('word(_,j)')';end;return lambda
fib: procedure; arg x; if x<2 then return x; s=0; a=0; b=1
do j=2 to x; s=a+b; a=b; b=s; end; return s
```

dfact: procedure; arg x; !=1; do j=x to 2 by -2;!=!*j; end; return ! tfact: procedure; arg x; !=1; do j=x to 2 by -3;!=!*j; end; return ! qfact: procedure; arg x; !=1; do j=x to 2 by -3;!=!*j; end; return !

```fact: procedure; arg x; !=1; do j=2 to x      ;!=!*j; end; return !
```

</lang> Output:

```fib
12586269025

fib
144 89 55 34 21 13 8 5 3 2 1 1 0

fact
120

Dfact
1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800

Dfact
8 15 48 105 384 945 3840 10395 46080 135135

Tfact
4 10 18 28 80 162 280 880 1944 3640

Qfact
4 10 18 28 80 26582634158080000

length
4 3 2 5 11

reverse
32 876 7001 54 SAM I AM

trunc
-7 12 3 6 78
```

## Ruby

<lang ruby>irb(main):001:0> Y = lambda {|f| lambda {|x| x[x]}[lambda {|y| f[lambda {|*args| y[y][*args]}]}]} => #<Proc:0xb7d3cae0@(irb):1> irb(main):002:0> fac = lambda {|f| lambda {|n| n<2 ? 1 : n*f[n-1]}} => #<Proc:0xb7d2b330@(irb):2> irb(main):003:0> Array.new(10) {|i| Y[fac][i]} => [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880] irb(main):004:0> fib = lambda {|f| lambda {|n| n == 0 ? 0 : n == 1 ? 1 : f[n-1] + f[n-2]}} => #<Proc:0xb7d0a1f8@(irb):4> irb(main):005:0> Array.new(10) {|i| Y[fib][i]} => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</lang>

## Scala

Credit goes to the thread in scala blog <lang scala> def Y[A,B](f: (A=>B)=>(A=>B)) = {

``` case class W(wf: W=>A=>B) {
def apply(w: W) = wf(w)
}
val g: W=>A=>B = w => f(w(w))(_)
g(W(g))
```

} </lang> Example <lang scala> val factorial = Y[Int, Int](f => i => if (i <= 0) 1 else f(i - 1) * i) </lang>

## Scheme

The Y combinator is useful only in those languages that provide a call-by-name evaluation strategy, since (Y f) diverges (for any f) in call-by-value settings. A version of the Y combinator that can be used in call-by-value evaluation is given by η-conversion of part of the ordinary Y combinator:

Z = λf. (λg. fx. g g x)) (λg. fx. g g x))

In Scheme this can be implemented as <lang scheme>(define Z

``` (lambda (f)
((lambda (g)
(f (lambda (x) ((g g) x))))
(lambda (g)
(f (lambda (x) ((g g) x)))))))
```

(define fac

``` (lambda (f)
(lambda (x)
(if (= x 0)
1
(* x (f (- x 1)))))))
```

(define fib

``` (lambda (f)
(lambda (x)
(if (< x 2)
x
(+ (f (- x 1)) (f (- x 2)))))))
```

(display ((Z fac) 30)) (newline)

(display ((Z fib) 30)) (newline)</lang> Output: <lang>265252859812191058636308480000000 832040</lang>

## Slate

The Y combinator is already defined in slate as:

<lang slate>Method traits define: #Y &builder:

``` [[| :f | [| :x | f applyWith: (x applyWith: x)]
```

applyWith: [| :x | f applyWith: (x applyWith: x)]]].</lang>

## Standard ML

<lang sml>- datatype 'a mu = Roll of ('a mu -> 'a)

``` fun unroll (Roll x) = x

fun fix f = (fn x => fn a => f (unroll x x) a) (Roll (fn x => fn a => f (unroll x x) a))

fun fac f 0 = 1
| fac f n = n * f (n-1)

fun fib f 0 = 0
| fib f 1 = 1
| fib f n = f (n-1) + f (n-2)
```

datatype 'a mu = Roll of 'a mu -> 'a val unroll = fn : 'a mu -> 'a mu -> 'a val fix = fn : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b val fac = fn : (int -> int) -> int -> int val fib = fn : (int -> int) -> int -> int - List.tabulate (10, fix fac); val it = [1,1,2,6,24,120,720,5040,40320,362880] : int list - List.tabulate (10, fix fib); val it = [0,1,1,2,3,5,8,13,21,34] : int list</lang>

## Tcl

Y combinator is derived in great detail here.

## Ursala

The standard y combinator doesn't work in Ursala due to eager evaluation, but an alternative is easily defined as shown <lang Ursala>(r "f") "x" = "f"("f","x") my_fix "h" = r ("f","x"). ("h" r "f") "x"</lang> or by this shorter expression for the same thing in point free form. <lang Ursala>my_fix = //~&R+ ^|H\~&+ ; //~&R</lang> Normally you'd like to define a function recursively by writing ${\displaystyle f=h(f)}$, where ${\displaystyle h(f)}$ is just the body of the function with recursive calls to ${\displaystyle f}$ in it. With a fixed point combinator such as `my_fix` as defined above, you do almost the same thing, except it's ${\displaystyle f=}$```my_fix "f".``` ${\displaystyle h}$`("f")`, where the dot represents lambda abstraction and the quotes signify a dummy variable. Using this method, the definition of the factorial function becomes <lang Ursala>#import nat

fact = my_fix "f". ~&?\1! product^/~& "f"+ predecessor</lang> To make it easier, the compiler has a directive to let you install your own fixed point combinator for it to use, which looks like this, <lang Ursala>#fix my_fix</lang> with your choice of function to be used in place of `my_fix`. Having done that, you may express recursive functions per convention by circular definitions, as in this example of a Fibonacci function. <lang Ursala>fib = {0,1}?</1! sum+ fib~~+ predecessor^~/~& predecessor</lang> Note that this way is only syntactic sugar for the for explicit way shown above. Without a fixed point combinator given in the `#fix` directive, this definition of fib would not have compiled. (Ursala allows user defined fixed point combinators because they're good for other things besides functions.) To confirm that all this works, here is a test program applying both of the functions defined above to the numbers from 1 to 8. <lang Ursala>#cast %nLW

examples = (fact* <1,2,3,4,5,6,7,8>,fib* <1,2,3,4,5,6,7,8>)</lang> output:

```(
<1,2,6,24,120,720,5040,40320>,
<1,2,3,5,8,13,21,34>)```

The fixed point combinator defined above is theoretically correct but inefficient and limited to first order functions, whereas the standard distribution includes a library (`sol`) providing a hierarchy of fixed point combinators suitable for production use and with higher order functions. A more efficient alternative implementation of `my_fix` would be `general_function_fixer 0` (with 0 signifying the lowest order of fixed point combinators), or if that's too easy, then by this definition. <lang Ursala>#import sol

1. fix general_function_fixer 1

my_fix "h" = "h" my_fix "h"</lang> Note that this equation is solved using the next fixed point combinator in the hierarchy.