Y combinator: Difference between revisions

 

In strict [[wp:Functional programming|functional programming]] and the [[wp:lambda calculus|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.

 

 

 

;Task:

 

 

=={{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:

</pre>

-->

 

=={{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

fib(9)=34

fib(10)=55</pre>

 

=={{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 () {

auto almost_fib = [] (auto f) { return

[=] (auto n) { return

auto almost_fac = [] (auto f) { return

[=] (auto n) { return

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

=={{header|Elena}}==

{{trans|Smalltalk}}

singleton YCombinator

public program()

{

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}}==

 

 

 

 

 

 

=={{header|Erlang}}==

 

Fac = fun (F) ->

end.

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

 

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

let unroll (Roll x) = x

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

// val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>

// Although true to the factorial definition, the

// recursive call is not in tail call position, so can't be optimized

//let fac = fix (fun f n -> if n < 2 then 1I else bigint n * f (n - 1))

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

// much better progressive calculation in tail call position...

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

// Although true to the definition of Fibonacci numbers,

// this can't be tail call optimized and recursively repeats calculations

// let fib = fix (fun fnc n -> if n < 2 then n else fnc (n - 1) + fnc (n - 2))

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

// much better progressive calculation in tail call position...

let fib = fix (fun fnc f s i -> if i < 2 then f else fnc s (f + s) (i - 1)) 1I 1I

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

// val fix : ((unit -> 'a) -> 'a -> 'a) = <fun>

 

let fac = fix (fun f n i -> if i < 2 then n else f () (bigint i * n) (i - 1)) <| 1I

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

 

let fib = fix (fun fnc f s i -> if i < 2 then f else fnc () s (f + s) (i - 1)) 1I 1I

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

type CIS<'a> = CIS of 'a * (unit -> CIS<'a>) // ' fix formatting

 

// it demonstrates something that can't be done with the Z-combinator...

let fibs() =

 

[<EntryPoint>]

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

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

printfn ""

{{output}}

<pre>3628800

55

 

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|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).

=={{header|J}}==

 

===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}}==

 

=={{header|Julia}}==

 

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

 

Usage:

 

 

 

1

2

3628800

 

1

1

34

55

 

=={{header|Kitten}}==

 

-> f; { f y } f call

 

5 \fac y say // 120

10 \fib y say // 55

 

=={{header|Kotlin}}==

 

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

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

println()

 

{{out}}

 

=={{header|Lambdatalk}}==

 

1) defining the Ycombinator

 

2) defining non recursive functions

 

3) testing

-> 720

-> 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 {

Ycombinator

 

Module Checkit {

}

Checkit

Module CheckRecursion {

}

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:

{ {extern "manool.org.18/std/0.3/all"} in

: let { Y = {proc {F} as {proc {X} as X[X]}[{proc {X} with {F} as F[{proc {Y} with {X} as X[X][Y]}]}]} } in

}

}

Using less syntactic sugar:

{ {extern "manool.org.18/std/0.3/all"} in

: let { Y = {proc {F} as {proc {X} as X[X]}[{proc {F; X} as F[{proc {X; Y} as X[X][Y]}.Bind[X]]}.Bind[F]]} } in

}

}

{{output}}

<pre>

 

=={{header|Maple}}==

> Y:=f->(x->x(x))(g->f((()->g(g)(args)))):

> Yfac:=Y(f->(x->`if`(x<2,1,x*f(x-1)))):

> seq( Yfib( i ), i = 1 .. 10 );

1, 1, 2, 3, 5, 8, 13, 21, 34, 55

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

factorial = Y[Function[f, If[# < 1, 1, # f[# - 1]] &]];

 

=={{header|Moonscript}}==

 

=={{header|Objective-C}}==

{{works with|Mac OS X|10.6+}}{{works with|iOS|4.0+}}

 

typedef int (^Func)(int);

}

return 0;

 

The usual version using recursion, disallowed by the task:

return ^(int x) {

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

};

 

=={{header|OCaml}}==

The Y-combinator over functions may be written directly in OCaml provided rectypes are enabled:

Polymorphic variants are the simplest workaround in the absence of rectypes:

Otherwise, an ordinary variant can be defined and used:

 

let unroll (Roll x) = x;;

 

fix fib 8;;

 

The usual version using recursion, disallowed by the task:

 

=={{header|Oforth}}==

 

With recursion into Y definition (so non stateless Y) :

 

Without recursion into Y definition (stateless Y).

 

Usage :

#almost-fact Y => fact

 

n 0 == ifTrue: [ 1 m 1 - f perform return ]

n 1 - m f perform m 1 - f perform ;

 

=={{header|Order}}==

 

#define ORDER_PP_DEF_8y \

 

ORDER_PP(8to_lit(8ap(8y(8fac), 10))) // 3628800

 

=={{header|Oz}}==

Y = fun {$ F}

{fun {$ X} {X X} end

in

{Show {Fac 5}}

 

=={{header|PARI/GP}}==

As of 2.8.0, GP cannot make general self-references in closures declared inline, so the Y combinator is required to implement these functions recursively in that environment, e.g., for use in parallel processing.

fact=Y((f,n)->if(n,n*f(f,n-1),1));

fib=Y((f,n)->if(n>1,f(f,n-1)+f(f,n-2),n));

apply(fact, [1..10])

{{out}}

<pre>%1 = [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]

 

=={{header|Perl}}==

sub { my $x = shift; $x->($x) }->( # (λx.x x)

sub {my $y = shift; $f->(sub {$y->($y)(@_)})} # λy.f λz.y y z

for my $f ($fac, $fib) {

print join(' ', map Y($f)->($_), 0..9), "\n";

{{out}}

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

 

The usual version using recursion, disallowed by the task:

sub {$f->(Y($f))->(@_)}

 

=={{header|Phix}}==

[[Partial_function_application#Phix|Partial_function_application]],

and/or [[Function_composition#Phix|Function_composition]]

{{out}}

<pre>

 

=={{header|Phixmonti}}==

 

def fac

 

getid fac "fac" test

 

=={{header|PHP}}==

{{works with|PHP|5.3+}}

function Y($f) {

$g = function($w) use($f) {

 

echo $factorial(10), "\n";

The usual version using recursion, disallowed by the task:

return function() use($f) {

return call_user_func_array($f(Y($f)), func_get_args());

};

 

{{works with|PHP|pre-5.3 and 5.3+}}

with <tt>create_function</tt> instead of real closures. A little far-fetched, but...

function Y($f) {

$g = create_function('$w', '$f = '.var_export($f,true).';

$factorial = Y('almost_fac');

echo $factorial(10), "\n";

 

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

{{works with|PHP|5.4+}}

function pseudoY($f) {

$g = function($w) use ($f) {

});

echo $fibonacci(10), "\n";

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

 

=={{header|PicoLisp}}==

{{trans|Common Lisp}}

(let X (curry (F) (Y) (F (curry (Y) @ (pass (Y Y)))))

===Factorial===

(de fact (F)

(curry (F) (N)

 

: ((Y fact) 6)

 

===Fibonacci sequence===

(de fibo (F)

(curry (F) (N)

 

: ((Y fibo) 22)

 

===Ackermann function===

(de ack (F)

(curry (F) (X Y)

 

: ((Y ack) 3 4)

 

=={{header|Pop11}}==

procedure (x); x(x) endprocedure(

procedure (y);

 

Y(fac)(5) =>

{{out}}

<pre>

{{trans|Joy}}

{{libheader|initlib}}

{dup cons} exch concat dup cons i

}.

{ {pop zero?} {pop succ} {{dup pred} dip i *} ifte }

y

 

=={{header|PowerShell}}==

Z & := & \lambda f.(\lambda x.f\ (\lambda y.x\ x\ y))\ (\lambda x.f\ (\lambda y.x\ x\ y)) \\

\end{array}</math>

param([ScriptBlock] $f)

invoke-expression @"

 

$Z.InvokeReturnAsIs($fac).InvokeReturnAsIs(5)

 

 

GetNewClosure() was added in Powershell 2, allowing for an implementation without metaprogramming. The following was tested with Powershell 4.

 

param ($f)

 

 

$Y.invoke($fact).invoke(5)

 

=={{header|Prolog}}==

The code is inspired from this page : http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord#Hiord (p 106). <br>

Original code is from <b>Hermenegildo</b> and al : <b>Hiord: A Type-Free Higher-Order Logic Programming Language with Predicate Abstraction</b>, pdf accessible here http://www.stups.uni-duesseldorf.de/asap/?id=129.

 

% The Y combinator

),

 

{{out}}

<pre>

 

=={{header|Python}}==

>>> fac = lambda f: lambda n: (1 if n<2 else n*f(n-1))

>>> [ Y(fac)(i) for i in range(10) ]

>>> 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) ]

 

The usual version using recursion, disallowed by the task:

 

 

=={{header|R}}==

 

 

 

 

=={{header|Racket}}==

 

The lazy implementation

 

(define Y (λ (f) ((λ (x) (f (x x))) (λ (x) (f (x x))))))

(Y (λ (fact) (λ (n) (if (zero? n) 1 (* n (fact (- n 1))))))))

(define Fib

 

{{out}}

 

Strict realization:

(define Y (λ (b) ((λ (f) (b (λ (x) ((f f) x))))

 

Definitions of <tt>Fact</tt> and <tt>Fib</tt> functions will be the same as in Lazy Racket.

 

Finally, a definition in Typed Racket is a little difficult as in other statically typed languages:

 

(: make-recursive : (All (S T) ((S -> T) -> (S -> T)) -> (S -> T)))

(* n (fact (- n 1))))))))

 

 

=={{header|Raku}}==

(formerly Perl 6)

sub fac (&f) { sub ($n) { $n < 2 ?? 1 !! $n * f($n - 1) } }

sub fib (&f) { sub ($n) { $n < 2 ?? $n !! f($n - 1) + f($n - 2) } }

{{out}}

<pre>(1 1 2 6 24 120 720 5040 40320 362880)

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

 

 

=={{header|REBOL}}==

;usage example

 

=={{header|REXX}}==

<pre>

fib 12586269025

Qfact 4 5 12 21 32 3805072588800

length 4 3 2 5 11

trunc -7 12 3 6 78

</pre>

 

Using a lambda:

 

lambda {|g| g[g]}[lambda do |g|

f[lambda {|*args| g[g][*args]}]

 

fib = lambda{|f| lambda{|n| n < 2 ? n : f[n-1] + f[n-2]}}

 

Same as the above, using the new short lambda syntax:

{{works with|Ruby|1.9}}

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

fib = ->(f) { ->(n) { n < 2 ? n : f.(n-2) + f.(n-1) } }

 

 

Using a method:

 

{{works with|Ruby|1.9}}

lambda do |g|

f.call {|*args| g[g][*args]}

# => [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

p Array.new(10) {|i| fib[i]}

 

The usual version using recursion, disallowed by the task:

lambda {|*args| f[y[f]][*args]}

 

=={{header|Rust}}==

 

 

trait Apply<T, R> {

}

 

}

 

}

 

fn fac(n: usize) -> usize {

}

 

}

 

}

 

{{output}}

 

=={{header|Scala}}==

}

g(W(g))

Example

fac(6) //> res0: Int = 720

 

 

=={{header|Scheme}}==

(lambda (f) ; (g g) = (f (lambda a (apply (g g) a)))

((lambda (g) (g g)) ; (Y f) == (f (lambda a (apply (Y f) a)))

 

(display (fib2 134))

{{out}}

<pre>720

If we were allowed to use recursion (with <code>Y</code> referring to itself by name in its body) we could define the equivalent to the above as

 

(lambda (f)

 

And another way is:

(lambda (f)

 

Which, non-recursively, is

(lambda (f) ; (g g) = (lambda a (apply (f (g g)) a))

((lambda (g) (g g)) ; (Y2 f) == (lambda a (apply (f (Y2 f)) a))

(lambda (g)

 

=={{header|Shen}}==

F -> ((/. X (X X))

(/. X (F (/. Z ((X X) Z))))))

(Fac 0)

(Fac 5)

{{out}}

<pre>1

 

=={{header|Sidef}}==

 

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

 

var fib = ->(f) { ->(n) { n < 2 ? n : (f(n-2) + f(n-1)) } }

{{out}}

<pre>

=={{header|Slate}}==

The Y combinator is already defined in slate as:

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

 

=={{header|Smalltalk}}==

{{works with|GNU Smalltalk}}

 

fib := Y value: [:f| [:i| i <= 1 ifTrue: [i] ifFalse: [(f value: i-1) + (f value: i-2)] ] ].

fact := Y value: [:f| [:i| i = 0 ifTrue: [1] ifFalse: [(f value: i-1) * i] ] ].

 

{{out}}

<pre>55

 

The usual version using recursion, disallowed by the task:

 

=={{header|Standard ML}}==

fun unroll (Roll x) = x

 

val it = [1,1,2,6,24,120,720,5040,40320,362880] : int list

- List.tabulate (10, fix fib);

 

The usual version using recursion, disallowed by the task:

 

=={{header|SuperCollider}}==

(

)

};

)

 

 

(

 

 

 

=={{header|Swift}}==

Using a recursive type:

let o : RecursiveFunc<F> -> F

}

}

println("fac(5) = \(fac(5))")

{{out}}

<pre>

Without a recursive type, and instead using <code>Any</code> to erase the type:

{{works with|Swift|1.2+}} (for Swift 1.1 replace <code>as!</code> with <code>as</code>)

typealias RecursiveFunc = Any -> A -> B

let r : RecursiveFunc = { (z: Any) in let w = z as! RecursiveFunc; return f { w(w)($0) } }

return r(r)

 

The usual version using recursion, disallowed by the task:

return { x in f(Y(f))(x) }

 

=={{header|Tailspin}}==

// YCombinator is not needed since tailspin supports recursion readily, but this demonstrates passing functions as parameters

end makeStep

end combinator

templates factorial

<=0> 1 !

<>

$ * ($ - 1 -> next) !

end seed

end factorial

templates fibonacci

<..1> $ !

<>

end seed

end fibonacci

5 -> fibonacci -> 'fibonacci 5: $;

' -> !OUT::write

{{out}}

<pre>

This prints out 24, the factorial of 4:

 

(defun y (f)

[(op @1 @1)

 

;; Test:

 

Both the <code>op</code> and <code>do</code> operators are a syntactic sugar for currying, in two different flavors. The forms within <code>do</code> that are symbols are evaluated in the normal Lisp-2 style and the first symbol can be an operator. Under <code>op</code>, any forms that are symbols are evaluated in the Lisp-2 style, and the first form is expected to evaluate to a function. The name <code>do</code> stems from the fact that the operator is used for currying over special forms like <code>if</code> in the above example, where there is evaluation control. Operators can have side effects: they can "do" something. Consider <code>(do set a @1)</code> which yields a function of one argument which assigns that argument to <code>a</code>.

 

 

=={{header|Ursala}}==

The standard y combinator doesn't work in Ursala due to eager

evaluation, but an alternative is easily defined as shown

or by this shorter expression for the same thing in point free form.

Normally you'd like to define a function recursively by writing

<math>f = h(f)</math>, where <math>h(f)</math> is just the body of the

quotes signify a dummy variable. Using this

method, the definition of the factorial function becomes

 

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,

with your choice of function to be used in place of <code>my_fix</code>.

Having done that, you may express recursive functions per convention by circular definitions,

as in this example of a Fibonacci function.

Note that this way is only syntactic sugar for the for explicit way

shown above. Without a fixed point combinator given in the <code>#fix</code>

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.

 

{{out}}

<pre>

(with 0 signifying the lowest order of fixed point combinators),

or if that's too easy, then by this definition.

 

#fix general_function_fixer 1

 

Note that this equation is solved using the next fixed point combinator in the hierarchy.

 

=={{header|Verbexx}}==

 

y @FN [f]

 

@LOOP init:{ i = -1} while:(i <= 16) next:{i++}

 

=={{header|Vim Script}}==

There is no lambda in Vim (yet?), so here is a way to fake it using a Dictionary. This also provides garbage collection.

 

func! Lambx(sig, expr, dict)

echo Callx(Callx(g:Y, [g:fac]), [5])

echo map(range(10), 'Callx(Callx(Y, [fac]), [v:val])')

Update: since Vim 7.4.2044 (or so...), the following can be used (the feature check was added with 7.4.2121):

if !has("lambda")

echoerr 'Lambda feature required'

echo Y(Fac)(5)

echo map(range(10), 'Y(Fac)(v:val)')

Output:

<pre>120

 

=={{header|Wart}}==

def (Y improver)

((fn(gen) gen.gen)

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

 

 

{{omit from|ACL2}}

{{omit from|PureBasic}}

{{omit from|TI-89 BASIC}} <!-- no lambdas, no first-class functions except by name string -->

 

=={{header|XQuery}}==

Version 3.0 of the [http://www.w3.org/TR/xpath-30/ XPath] and [http://www.w3.org/TR/xquery-30/ XQuery] specifications added support for function items.

 

(function($x) { ($x)($x) })( function($g) { $f( (function($a) { $g($g) ($a)}) ) } )

}

$fib(6)

)

{{out}}

 

=={{header|zkl}}==

Functions don't get to look outside of their scope so data in enclosing scopes needs to be bound to a function, the fp (function application/cheap currying) method does this. 'wrap is syntactic sugar for fp.

Y(almost_factorial)(6).println();

{{out}}

<pre>

L(1,1,2,6,24,120,720,5040,40320,362880,3628800)

</pre>

Y(almost_fib)(9).println();

{{out}}

<pre>