Y combinator: Difference between revisions

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program Ycombi64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

=={{header|ALGOL 68}}==

{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - compile not currently available on my system.}}

{{wont work with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny] - correctly detects a scope violation}} -->

MODE F = PROC(INT)INT;

MODE Y = PROC(Y)F;

FOR i TO 10 DO print(y(fib)(i)) OD

<!--

ALGOL 68G Output demonstrating the runtime scope violation:

These could easily be fixed by changing names, but I believe that doing so would make the code harder to follow.

# This version needs partial parameterisation in order to work #

print( newline )

=={{header|AppleScript}}==

The identifier used for Y uses "pipe quoting" to make it obviously distinct from the y used inside the definition.

on |Y|(f)

end script

end if

{{Out}}

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

.include "../affichage.inc"

{{output}}

<pre>

=={{header|ATS}}==

(* ****** ****** *)

//

//

(* ****** ****** *)

=={{header|BlitzMax}}==

BlitzMax doesn't support anonymous functions or classes, so everything needs to be explicitly named.

'Boxed type so we can just use object arrays for argument lists

Local fib:Func = Func(_Y.apply([FibL1.lambda(Null)]))

=={{header|Bracmat}}==

<pre>(Y H) i</pre>

where i varies between 1 and 10, are translated into Bracmat as shown below

= /(

' ( g

)

&

{{out}}

<pre>1!=1

=={{header|C}}==

#include <stdlib.h>

return 0;

}

{{out}}

''Note: in the code, <code>Func<T, TResult></code> is a delegate type (the CLR equivalent of a function pointer) that has a parameter of type <code>T</code> and return type of <code>TResult</code>. See [[Higher-order functions#C#]] or [https://docs.microsoft.com/en-us/dotnet/standard/delegates-lambdas the documentation] for more information.''

static class YCombinator<T, TResult>

}

}

{{out}}

<pre>3628800

Alternatively, with a non-generic holder class (note that <code>Fix</code> is now a method, as properties cannot be generic):

{

private delegate Func<T, TResult> RecursiveFunc<T, TResult>(RecursiveFunc<T, TResult> r);

public static Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f)

=> ((RecursiveFunc<T, TResult>)(g => f(x => g(g)(x))))(g => f(x => g(g)(x)));

Using the late-binding offered by <code>dynamic</code> to eliminate the recursive type:

{

public static Func<Func<Func<T, TResult>, Func<T, TResult>>, Func<T, TResult>> Fix { get; } =

f => ((Func<dynamic, Func<T, TResult>>)(g => f(x => g(g)(x))))((Func<dynamic, Func<T, TResult>>)(g => f(x => g(g)(x))));

The usual version using recursion, disallowed by the task (implemented as a generic method):

{

static Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f) => x => f(Fix(f))(x);

===Translations===

'''Verbatim'''

using FuncFunc = System.Func<System.Func<int, int>, System.Func<int, int>>;

return 0;

}

'''Semi-idiomatic'''

using FuncFunc = System.Func<System.Func<int, int>, System.Func<int, int>>;

Console.WriteLine("fac(10) = " + fac(10));

}

====[http://rosettacode.org/mw/index.php?oldid=287744#Ceylon Ceylon]====

'''Verbatim'''

using System.Diagnostics;

Console.WriteLine(fibY1(10)); // 110

}

'''Semi-idiomatic'''

using System.Diagnostics;

Console.WriteLine(fibY1(10));

}

====[http://rosettacode.org/mw/index.php?oldid=287744#Go Go]====

'''Verbatim'''

// Func and FuncFunc can be defined using using aliases and the System.Func<T, TReult> type, but RecursiveFunc must be a delegate type of its own.

};

}

Recursive:

return delegate (int x) {

return f(Y(f))(x);

};

'''Semi-idiomatic'''

delegate int Func(int i);

static Func almost_fib(Func f) => x => x <= 2 ? 1 : f(x - 1) + f(x - 2);

Recursive:

====[http://rosettacode.org/mw/index.php?oldid=287744#Java Java]====

Since Java uses interfaces and C# uses delegates, which are the only type that the C# compiler will coerce lambda expressions to, this code declares a <code>Functions</code> class for providing a means of converting CLR delegates to objects that implement the <code>Function</code> and <code>RecursiveFunction</code> interfaces.

static class Program {

Console.WriteLine("fac(10) = " + fac.apply(10));

}

'''"Idiomatic"'''

For demonstrative purposes, to completely avoid using CLR delegates, lambda expressions can be replaced with explicit types that implement the functional interfaces. Closures are thus implemented by replacing all usages of the original local variable with a field of the type that represents the lambda expression; this process, called "hoisting" is actually how variable capturing is implemented by the C# compiler (for more information, see [https://blogs.msdn.microsoft.com/abhinaba/2005/10/18/c-anonymous-methods-are-not-closures/ this Microsoft blog post].

static class YCombinator {

Console.WriteLine("fac(10) = " + fac.apply(10));

}

'''C# 1.0'''

To conclude this chain of decreasing reliance on language features, here is above code translated to C# 1.0. The largest change is the replacement of the generic interfaces with the results of manually substituting their type parameters.

class Program {

Console.WriteLine("fac(10) = " + fac.apply(10));

}

'''Modified/varargs (the last implementation in the Java section)'''

Since C# delegates cannot declare members, extension methods are used to simulate doing so.

using System.Collections.Generic;

using System.Linq;

).ForAll(Console.WriteLine);

}

====[http://rosettacode.org/mw/index.php?oldid=287744#Swift Swift]====

The more idiomatic version doesn't look much different.

static class Program {

Console.WriteLine($"fib(9) = {fib(9)}");

}

Without recursive type:

Func<dynamic, Func<A, B>> r = z => { var w = (Func<dynamic, Func<A, B>>)z; return f(_0 => w(w)(_0)); };

return r(r);

Recursive:

return x => f(Y(f))(x);

=={{header|C++}}==

Known to work with GCC 4.7.2. Compile with

g++ --std=c++11 ycomb.cc

#include <functional>

std::cout << "fac(10) = " << fac(10) << std::endl;

return 0;

{{out}}

A shorter version, taking advantage of generic lambdas. Known to work with GCC 5.2.0, but likely some earlier versions as well. Compile with

g++ --std=c++14 ycomb.cc

#include <functional>

int main () {

std:: cout << fib (10) << '\n'

<< fac (10) << '\n';

{{out}}

The usual version using recursion, disallowed by the task:

std::function<B(A)> Y (std::function<std::function<B(A)>(std::function<B(A)>)> f) {

return [f](A x) {

return f(Y(f))(x);

};

Another version which is disallowed because a function passes itself, which is also a kind of recursion:

struct YFunctor {

const std::function<std::function<B(A)>(std::function<B(A)>)> f;

std::function<B(A)> Y (std::function<std::function<B(A)>(std::function<B(A)>)> f) {

return YFunctor<A,B>(f);

=={{header|Ceylon}}==

Using a class for the recursive type:

Result(*Args)(Result(*Args)) f)

given Args satisfies Anything[] {

print(factorialY1(10)); // 3628800

Using Anything to erase the function type:

Result(*Args)(Result(*Args)) f)

given Args satisfies Anything[] {

return r(r);

Using recursion, this does not satisfy the task requirements, but is included here for illustrative purposes:

Result(*Args)(Result(*Args)) f)

given Args satisfies Anything[]

=={{header|Chapel}}==

{{works with|Chapel version 1.24.1}}

record InnerFunc {

const xi;

writeln(facz(10));

{{out}}

<pre>3628800

{{works with|Chapel version 1.24.1}}

/*

proc fixy(f) {

writeln(facy(10));

The output is the same as the above.

=={{header|Clojure}}==

((fn [x] (x x))

(fn [x]

1 1

(+ (f (dec n))

{{out}}

<code>Y</code> can be written slightly more concisely via syntax sugar:

=={{header|CoffeeScript}}==

or

fib = Y( (f) -> (n) -> if n > 1 then f(n-1) + f(n-2) else n )

=={{header|Common Lisp}}==

((lambda (g) (funcall g g))

(lambda (g)

? (mapcar #'fib '(1 2 3 4 5 6 7 8 9 10))

=={{header|Crystal}}==

The following Crystal code implements the name-recursion Y-Combinator without assuming that functions are recursive (which in Crystal they actually are):

struct RecursiveFunc(T) # a generic recursive function wrapper...

puts fac(10)

The "horrendously inefficient" massively repetitious implementations can be made much more efficient by changing the implementation for the two functions as follows:

facp = -> (fn : Proc(BigInt -> (Int32 -> BigInt))) {

-> (n : BigInt) { -> (i : Int32) {

i < 2 ? f : fn.call.call(s).call(f + s).call(i - 1) } } } }

YCombo.new(fibp).fixy.call(BigInt.new).call(BigInt.new(1)).call(x)

Finally, since Crystal function's/"def"'s can call themselves recursively, the implementation of the Y-Combinator can be changed to use this while still being "call by name" (not value/variable recursion) as follows; this uses the identical lambda "Proc"'s internally with just the application to the Y-Combinator changed:

f.call(-> { ycombo(f) })

end

i < 2 ? f : fn.call.call(s).call(f + s).call(i - 1) } } } }

ycombo(fibp).call(BigInt.new).call(BigInt.new(1)).call(x)

All versions produce the same output:

=={{header|D}}==

A stateless generic Y combinator:

auto Y(S, T...)(S delegate(T) delegate(S delegate(T)) f) {

writeln("factorial: ", 10.iota.map!factorial);

writeln("ackermann(3, 5): ", ackermann(3, 5));

{{out}}

<pre>factorial: [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

{{trans|C++}}

(The translation is not literal; e.g. the function argument type is left unspecified to increase generality.)

{$APPTYPE CONSOLE}

Writeln ('Fib(10) = ', Fib (10));

Writeln ('Fac(10) = ', Fac (10));

=={{header|Dhall}}==

Here's an example using Natural/Fold to define recursive definitions of fibonacci and factorial:

: ∀(b : Type) → ∀(a : Type) → a → b → a

= λ(r : Type) → λ(a : Type) → λ(x : a) → λ(y : r) → x

n

The above dhall file gets rendered down to:

, 12586269025

=={{header|Déjà Vu}}==

{{trans|Python}}

labda y:

labda:

!. fac 6

{{out}}

<pre>720

=={{header|E}}==

{{trans|Python}}

def fac := fn f { fn n { if (n<2) {1} else { n*f(n-1) } }}

? 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)) }

=={{header|EchoLisp}}==

;; Ref : http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html

(fact 10)

→ 3628800

=={{header|Eero}}==

Translated from Objective-C example on this page.

typedef int (^Func)(int)

Log('fac(10) = %d', fac(10))

=={{header|Ela}}==

fac _ 0 = 1

fib f n = f (n - 1) + f (n - 2)

{{out}}

{{trans|Smalltalk}}

ELENA 4.x :

singleton YCombinator

console.printLine("fib(10)=",fib(10));

console.printLine("fact(10)=",fact(10));

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Python}}

iex(1)> yc = fn f -> (fn x -> x.(x) end).(fn y -> f.(fn arg -> y.(y).(arg) end) end) end

#Function<6.90072148/1 in :erl_eval.expr/5>

iex(5)> for i <- 0..9, do: yc.(fib).(i)

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

=={{header|Elm}}==

Note: the Fibonacci sequence is defined to start with zero or one, with the first exactly the same but with a zero prepended; these Fibonacci calculations use the second definition.

import Html exposing ( Html, text )

++ " " ++ String.fromInt (facy 10) ++ " " ++ String.fromInt (fiby 10)

++ " " ++ nCISs2String 20 (fibs())

{{out}}

<pre>3628800 55 3628800 55 ( 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 )</pre>

=={{header|Erlang}}==

Fac = fun (F) ->

end.

(Y(Fac))(5). %% 120

=={{header|F Sharp|F#}}==

let unroll (Roll x) = x

fac 10 |> printfn "%A" // prints 3628800

fib 10 |> printfn "%A" // prints 55

{{output}}

<pre>3628800

Also note that the above isn't the true fix point Y-combinator which would race without the beta conversion to the Z-combinator with the included `a` argument; the Z-combinator can't be used in all cases that require a true Y-combinator such as in the formation of deferred execution sequences in the last example, as follows:

type 'a mu = Roll of ('a mu -> 'a) // ' fixes ease syntax colouring confusion with

fibs() |> Seq.take 20 |> Seq.iter (printf "%A ")

printfn ""

{{output}}

<pre>3628800

The above would be useful if F# did not have recursive functions (functions that can call themselves in their own definition), but as for most modern languages, F# does have function recursion by the use of the `rec` keyword before the function name, thus the above `fac` and `fib` functions can be written much more simply (and to run faster using tail recursion) with a recursion definition for the `fix` Y-combinator as follows, with a simple injected deferred execution to prevent race:

// val fix : f:((unit -> 'a) -> 'a) -> 'a

Using the Y-combinator (or Z-combinator) as expressed here is pointless as in unnecessary and makes the code slower due to the extra function calls through the call stack, with the first non-function recursive implementation even slower than the second function recursion one; a non Y-combinator version can use function recursion with tail call optimization to simplify looping for about 100 times the speed in the actual loop overhead; thus, this is primarily an intellectual exercise.

=={{header|Factor}}==

In rosettacode/Y.factor

IN: rosettacode.Y

: Y ( quot -- quot )

: almost-fib ( quot -- quot )

In rosettacode/Y-tests.factor

IN: rosettacode.Y.tests

[ 120 ] [ 5 [ almost-fac ] Y call ] unit-test

running the tests :

<pre> ( scratchpad - auto ) "rosettacode.Y" test

=={{header|Falcon}}==

Y = { f => {x=> {n => f(x(x))(n)}} ({x=> {n => f(x(x))(n)}}) }

facStep = { f => {x => x < 1 ? 1 : x*f(x-1) }}

> "Factorial 10: ", YFac(10)

> "Fibonacci 10: ", YFib(10)

=={{header|Forth}}==

variable 'xt

\ Make room for an xt.

: y, ( xt1 -- xt2 ) >r :noname @xt, r> compile, postpone ; ;

\ Make a new instance of the Y combinator.

Samples:

10 :noname ( u1 xt -- u2 ) over ?dup if 1- swap execute * else 2drop 1 then ;

y execute . 3628800 ok

10 :noname ( u1 xt -- u2 ) over 2 < if drop else >r 1- dup r@ execute swap 1- r> execute + then ;

y execute . 55 ok

=={{header|FreeBASIC}}==

FreeBASIC does not support nested functions, lambda expressions or functions inside nested types

Y = f

End Function

test("fac")

test("fib")

{{out}}

<pre>fac: 1 2 6 24 120 720 5040 40320 362880 3628800

=={{header|GAP}}==

local u;

u := x -> x(x);

Y(fac)(8);

=={{header|Genyris}}==

{{trans|Scheme}}

function (n)

if (equal? n 0) 1

assertEqual ((Y fac) 5) 120

=={{header|Go}}==

import "fmt"

return f(x-1)+f(x-2)

}

{{out}}

<pre>

The usual version using recursion, disallowed by the task:

return func(x int) int {

return f(Y(f))(x)

}

=={{header|Groovy}}==

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

def factorial = Y { fac ->

}

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 '''''le'''ngth'' function.

A variadic version of Y in Groovy looks like this:

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

1.upto(10) {

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

=={{header|Haskell}}==

The obvious definition of the Y combinator <code>(\f-> (\x -> f (x x)) (\x-> f (x x)))</code> cannot be used in Haskell because it contains an infinite recursive type (<code>a = a -> b</code>). Defining a data type (Mu) allows this recursion to be broken.

{ unroll :: Mu a -> a }

[ map fac [1 .. 20]

, take 20 $ fibs()

The usual version uses recursion on a binding, disallowed by the task, to define the <code>fix</code> itself; but the definitions produced by this <code>fix</code> does ''not'' use recursion on value bindings although it does use recursion when defining a function (not possible in all languages), so it can be viewed as a true Y-combinator too:

-- thus its use just means that the recursion has been "pulled" into the "fix" function,

-- instead of the function that uses it...

, map fib [1 .. 20]

, take 20 fibs()

Now just because something is possible using the Y-combinator doesn't mean that it is practical: the above implementations can't compute much past the 1000th number in the Fibonacci list sequence and is quite slow at doing so; using direct function recursive routines compute about 100 times faster and don't hang for large ranges, nor give problems compiling as the first version does (GHC version 8.4.3 at -O1 optimization level).

===Non-tacit version===

Unfortunately, in principle, J functions cannot take functions of the same type as arguments. In other words, verbs (functions) cannot take verbs, and adverbs or conjunctions (higher-order functions) cannot take adverbs or conjunctions. This implementation uses the body, a literal (string), of an explicit adverb (a higher-order function with a left argument) as the argument for Y, to represent the adverb for which the product of Y is a fixed-point verb; Y itself is also an adverb.

(1 : (m,'u'))(1 : (m,'''u u`:6('',(5!:5<''u''),'')`:6 y'''))(1 :'u u`:6')

)

This Y combinator follows the standard method: it produces a fixed-point which reproduces and transforms itself anonymously according to the adverb represented by Y's argument. All names (variables) refer to arguments of the enclosing adverbs and there are no assignments.

The factorial and Fibonacci examples follow:

3628800

'(u@:<:@:<: + u@:<:)^:(1 < ])' Y 10 NB. Fibonacci

The names u, x, and y are J's standard names for arguments; the name y represents the argument of u and the name u represents the verb argument of the adverb for which Y produces a fixed-point. Any verb can also be expressed tacitly, without any reference to its argument(s), as in the Fibonacci example.

A structured derivation of a Y with states follows (the stateless version can be produced by replacing all the names by its referents):

ara=. 1 :'arb u' NB. The verb arb as an adverb

gab=. 1 :'u u`:6' NB. The AR of the adverb and the adverb itself as a train

The adverb Y, apart from using a representation as Y's argument, satisfies the task's requirements. However, it only works for monadic verbs (functions with a right argument). J's verbs can also be dyadic (functions with a left and right arguments) and ambivalent (almost all J's primitive verbs are ambivalent; for example - can be used as in - 1 and 2 - 1). The following adverb (XY) implements anonymous recursion of monadic, dyadic, and ambivalent verbs (the name x represents the left argument of u),

The following are examples of anonymous dyadic and ambivalent recursions,

3 4 5 6 7

5 7 9 11 13

8 11 20 41 86 179 368

NB. OEIS A097813 - main diagonal

J supports directly anonymous tacit recursion via the verb $: and for tacit recursions, XY is equivalent to the adverb,

===Tacit version===

The Y combinator can be implemented indirectly using, for example, the linear representations of verbs (Y becomes a wrapper which takes an ad hoc verb as an argument and serializes it; the underlying self-referring system interprets the serialized representation of a verb as the corresponding verb):

The factorial and Fibonacci examples:

n=. ] NB. Argument (right)

sr=. [ apply f. ,&< NB. Self referring

Fib=. ((u sr n - 2:) + u sr n - 1:) ^: (1 < n)

Fib f. Y 10

The stateless functions are shown next (the f. adverb replaces all embedded names by its referents):

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

Fib f. NB. Fibonacci step...

A structured derivation of Y follows:

lv=. (((^:_1)b.)(`(<'0';_1)))(`:6) NB. Linear representation of a verb argument

Y=. (&>)/lv(&sr) NB. Y with embedded states

Y=. 'Y'f. NB. Fixing it...

Y NB. ... To make it stateless (i.e., a combinator)

===Explicit alternate implementation===

Another approach:

f=. u Defer

(5!:1<'f') f y

if. 2 > y do. y

else. (x`:6 y-1) + x`:6 y-2 end.

Example use:

362880

almost_fibonacci Y 9

34

almost_fibonacci Y"0 i. 10

Or, if you would prefer to not have a dependency on the definition of Defer, an equivalent expression would be:

NB. this block will be n in the second part

:

f=. u (1 :n)

(5!:1<'f') f y

That said, if you think of association with a name as state (because in different contexts the association may not exist, or may be different) you might also want to remove that association in the context of the Y combinator.

For example:

=={{header|Java}}==

{{works with|Java|8+}}

public interface YCombinator {

System.out.println("fac(10) = " + fac.apply(10));

}

{{out}}

<pre>

</pre>

The usual version using recursion, disallowed by the task:

return x -> f.apply(Y(f)).apply(x);

Another version which is disallowed because a function passes itself, which is also a kind of recursion:

return new Function<A,B>() {

public B apply(A x) {

}

};

{{works with|Java|pre-8}}

We define a generic function interface like Java 8's <code>Function</code>.

public B call(A x);

}

System.out.println("fac(10) = " + fac.call(10));

}

The following code modifies the Function interface such that multiple parameters (via varargs) are supported, simplifies the y function considerably, and the [[Ackermann function#Java|Ackermann function]] has been included in this implementation (mostly because both [[Y combinator#D|D]] and [[Y combinator#PicoLisp|PicoLisp]] include it in their own implementations).

@FunctionalInterface

return apply(this);

}

import java.util.function.UnaryOperator;

@FunctionalInterface

import java.util.Optional;

import java.util.function.Function;

return inputs -> apply((INPUTS[]) Arrays.stream(inputs).parallel().map(transformer).toArray());

}

import java.math.BigInteger;

import java.util.Arrays;

).forEach(System.out::println);

}

{{out}} (may depend on which function gets processed first):

ackermann[3, 2] = 29

=={{header|JavaScript}}==

The standard version of the Y combinator does not use lexically bound local variables (or any local variables at all), which necessitates adding a wrapper function and some code duplication - the remaining locale variables are only there to make the relationship to the previous implementation more explicit:

var g = f((function(h) {

return function() {

return n > 1 ? f(n - 1) + f(n - 2) : n;

};

Changing the order of function application (i.e. the place where <code>f</code> gets called) and making use of the fact that we're generating a fixed-point, this can be reduced to

return (function(h) {

return h(h);

});

});

A functionally equivalent version using the implicit <code>this</code> parameter is also possible:

return (function(h) {

return h(h);

var fib = pseudoY(function(n) {

return n > 1 ? this(n - 1) + this(n - 2) : n;

However, <code>pseudoY()</code> is not a fixed-point combinator.

The usual version using recursion, disallowed by the task:

return function() {

return f(Y(f)).apply(this, arguments);

};

Another version which is disallowed because it uses <code>arguments.callee</code> for a function to get itself recursively:

return function() {

return f(arguments.callee).apply(this, arguments);

};

===ECMAScript 2015 (ES6) variants===

Since ECMAScript 2015 (ES6) just reached final draft, there are new ways to encode the applicative order Y combinator.

These use the new fat arrow function expression syntax, and are made to allow functions of more than one argument through the use of new rest parameters syntax and the corresponding new spread operator syntax. Also showcases new default parameter value syntax:

Y= // Except for the η-abstraction necessary for applicative order languages, this is the formal Y combinator.

f=>((g=>(f((...x)=>g(g)(...x))))

fact=>(n,m=1)=>n<2?m:fact(n-1,n*m);

tailfact= // Tail call version of factorial function

ECMAScript 2015 (ES6) also permits a really compact polyvariadic variant for mutually recursive functions:

polyfix= // A version that takes an array instead of multiple arguments would simply use l instead of (...l) for parameter

(...l)=>(

polyfix(

(even,odd)=>n=>(n===0)||odd(n-1),

A minimalist version:

=={{header|Joy}}==

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

=={{header|Julia}}==

_

_ _ _(_)_ | Documentation: https://docs.julialang.org

Y = f -> (x -> x(x))(y -> f((t...) -> y(y)(t...)))

Y

Usage:

julia> fac = f -> (n -> n < 2 ? 1 : n * f(n - 1))

#9 (generic function with 1 method)

34

55

=={{header|Kitten}}==

-> f; { f y } f call

5 \fac y say // 120

10 \fib y say // 55

=={{header|Klingphix}}==

dup 1 great [dup 1 sub fac mult] if

;

@fac "fac" test

{{out}}

<pre>fib: 1 1 2 3 5 8 13 21 34 55

=={{header|Kotlin}}==

typealias Func<T, R> = (T) -> R

for (i in 1..10) print("${y(::fib)(i)} ")

println()

{{out}}

Tested in http://lambdaway.free.fr/lambdawalks/?view=Ycombinator

1) defining the Ycombinator

{def Y {lambda {:f} {:f :f}}}

-> 34

=={{header|Lua}}==

return function(...)

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

end

end

Usage:

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)

=={{header|M2000 Interpreter}}==

Lambda functions in M2000 are value types. They have a list of closures, but closures are copies, except for those closures which are reference types. Lambdas can keep state in closures (they are mutable). But here we didn't do that. Y combinator is a lambda which return a lambda with a closure as f function. This function called passing as first argument itself by value.

Module Ycombinator {

\\ y() return value. no use of closure

}

Ycombinator

Module Checkit {

Rem {

}

CheckRecursion

=={{header|MANOOL}}==

Here one additional technique is demonstrated: the Y combinator is applied to a function ''during compilation'' due to the <code>$</code> operator, which is optional: