Y combinator: Difference between revisions
m
syntax highlighting fixup automation
m (→{{header|Joy}}) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 22:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program Ycombi64.s */
Line 287:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|ALGOL 68}}==
Line 296:
{{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;
Line 306:
FOR i TO 10 DO print(y(fib)(i)) OD
END</
<!--
ALGOL 68G Output demonstrating the runtime scope violation:
Line 325:
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 #
Line 401:
print( newline )
END</
=={{header|AppleScript}}==
Line 411:
The identifier used for Y uses "pipe quoting" to make it obviously distinct from the y used inside the definition.
<
on |Y|(f)
Line 507:
end script
end if
end mReturn</
{{Out}}
<
fibs:{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765}}</
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
Line 767:
.include "../affichage.inc"
</syntaxhighlight>
{{output}}
<pre>
Line 797:
=={{header|ATS}}==
<syntaxhighlight lang="ats">
(* ****** ****** *)
//
Line 822:
//
(* ****** ****** *)
</syntaxhighlight>
=={{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
Line 981:
Local fib:Func = Func(_Y.apply([FibL1.lambda(Null)]))
Print Integer(fib.apply([Integer.Make(10)])).val</
=={{header|Bracmat}}==
Line 999:
<pre>(Y H) i</pre>
where i varies between 1 and 10, are translated into Bracmat as shown below
<
= /(
' ( g
Line 1,042:
)
&
)</
{{out}}
<pre>1!=1
Line 1,066:
=={{header|C}}==
C doesn't have first class functions, so we demote everything to second class to match.<
#include <stdlib.h>
Line 1,136:
return 0;
}
</syntaxhighlight>
{{out}}
Line 1,150:
''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>
Line 1,172:
}
}
</syntaxhighlight>
{{out}}
<pre>3628800
Line 1,178:
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);
Line 1,184:
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===
Line 1,206:
'''Verbatim'''
<
using FuncFunc = System.Func<System.Func<int, int>, System.Func<int, int>>;
Line 1,246:
return 0;
}
}</
'''Semi-idiomatic'''
<
using FuncFunc = System.Func<System.Func<int, int>, System.Func<int, int>>;
Line 1,275:
Console.WriteLine("fac(10) = " + fac(10));
}
}</
====[http://rosettacode.org/mw/index.php?oldid=287744#Ceylon Ceylon]====
Line 1,283:
'''Verbatim'''
<
using System.Diagnostics;
Line 1,330:
Console.WriteLine(fibY1(10)); // 110
}
}</
'''Semi-idiomatic'''
<
using System.Diagnostics;
Line 1,376:
Console.WriteLine(fibY1(10));
}
}</
====[http://rosettacode.org/mw/index.php?oldid=287744#Go Go]====
Line 1,382:
'''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.
Line 1,424:
};
}
}</
Recursive:
<
return delegate (int x) {
return f(Y(f))(x);
};
}</
'''Semi-idiomatic'''
<
delegate int Func(int i);
Line 1,456:
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]====
Line 1,466:
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 {
Line 1,514:
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 {
Line 1,609:
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 {
Line 1,710:
Console.WriteLine("fac(10) = " + fac.apply(10));
}
}</
'''Modified/varargs (the last implementation in the Java section)'''
Line 1,716:
Since C# delegates cannot declare members, extension methods are used to simulate doing so.
<
using System.Collections.Generic;
using System.Linq;
Line 1,844:
).ForAll(Console.WriteLine);
}
}</
====[http://rosettacode.org/mw/index.php?oldid=287744#Swift Swift]====
Line 1,852:
The more idiomatic version doesn't look much different.
<
static class Program {
Line 1,872:
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++}}==
Line 1,889:
Known to work with GCC 4.7.2. Compile with
g++ --std=c++11 ycomb.cc
<
#include <functional>
Line 1,931:
std::cout << "fac(10) = " << fac(10) << std::endl;
return 0;
}</
{{out}}
Line 1,942:
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 () {
Line 1,962:
std:: cout << fib (10) << '\n'
<< fac (10) << '\n';
}</
{{out}}
Line 1,971:
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;
Line 1,991:
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[] {
Line 2,016:
print(factorialY1(10)); // 3628800
print(fibY1(10)); // 110</
Using Anything to erase the function type:
<
Result(*Args)(Result(*Args)) f)
given Args satisfies Anything[] {
Line 2,029:
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[]
=> flatten((Args args) => f(y3(f))(*args));</
=={{header|Chapel}}==
Line 2,042:
{{works with|Chapel version 1.24.1}}
<
record InnerFunc {
const xi;
Line 2,077:
writeln(facz(10));
writeln(fibz(10));</
{{out}}
<pre>3628800
Line 2,085:
{{works with|Chapel version 1.24.1}}
<
/*
proc fixy(f) {
Line 2,132:
writeln(facy(10));
writeln(fibz(10));</
The output is the same as the above.
=={{header|Clojure}}==
<
((fn [x] (x x))
(fn [x]
Line 2,154:
1 1
(+ (f (dec n))
(f (dec (dec n))))))))</
{{out}}
Line 2,164:
<code>Y</code> can be written slightly more concisely via syntax sugar:
<
(#(% %) #(f (fn [& args] (apply (% %) args)))))</
=={{header|CoffeeScript}}==
<
or
<
<
fib = Y( (f) -> (n) -> if n > 1 then f(n-1) + f(n-2) else n )
</syntaxhighlight>
=={{header|Common Lisp}}==
<
((lambda (g) (funcall g g))
(lambda (g)
Line 2,204:
? (mapcar #'fib '(1 2 3 4 5 6 7 8 9 10))
(1 1 2 3 5 8 13 21 34 55)</
=={{header|Crystal}}==
Line 2,212:
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...
Line 2,242:
puts fac(10)
puts fib(11) # starts from 0 not 1!</
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) {
Line 2,258:
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)
end</
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
Line 2,278:
i < 2 ? f : fn.call.call(s).call(f + s).call(i - 1) } } } }
ycombo(fibp).call(BigInt.new).call(BigInt.new(1)).call(x)
end</
All versions produce the same output:
Line 2,287:
=={{header|D}}==
A stateless generic Y combinator:
<
auto Y(S, T...)(S delegate(T) delegate(S delegate(T)) f) {
Line 2,311:
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]
Line 2,321:
{{trans|C++}}
(The translation is not literal; e.g. the function argument type is left unspecified to increase generality.)
<
{$APPTYPE CONSOLE}
Line 2,387:
Writeln ('Fib(10) = ', Fib (10));
Writeln ('Fac(10) = ', Fac (10));
end.</
=={{header|Dhall}}==
Line 2,395:
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
Line 2,439:
n
in [fac 50, fib 50]</
The above dhall file gets rendered down to:
<
, 12586269025
]</
=={{header|Déjà Vu}}==
{{trans|Python}}
<
labda y:
labda:
Line 2,475:
!. fac 6
!. fib 6</
{{out}}
<pre>720
Line 2,482:
=={{header|E}}==
{{trans|Python}}
<
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) } }}</
<
? 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]</
=={{header|EchoLisp}}==
<
;; Ref : http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html
Line 2,518:
(fact 10)
→ 3628800
</syntaxhighlight>
=={{header|Eero}}==
Translated from Objective-C example on this page.
<
typedef int (^Func)(int)
Line 2,550:
Log('fac(10) = %d', fac(10))
return 0</
=={{header|Ela}}==
<
fac _ 0 = 1
Line 2,562:
fib f n = f (n - 1) + f (n - 2)
(fix fac 12, fix fib 12)</
{{out}}
Line 2,570:
{{trans|Smalltalk}}
ELENA 4.x :
<
singleton YCombinator
Line 2,585:
console.printLine("fib(10)=",fib(10));
console.printLine("fact(10)=",fact(10));
}</
{{out}}
<pre>
Line 2,594:
=={{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>
Line 2,605:
iex(5)> for i <- 0..9, do: yc.(fib).(i)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
</syntaxhighlight>
=={{header|Elm}}==
Line 2,613:
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 )
Line 2,687:
++ " " ++ String.fromInt (facy 10) ++ " " ++ String.fromInt (fiby 10)
++ " " ++ nCISs2String 20 (fibs())
|> text</
{{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) ->
Line 2,706:
end.
(Y(Fac))(5). %% 120
(Y(Fib))(8). %% 21</
=={{header|F Sharp|F#}}==
<
let unroll (Roll x) = x
Line 2,743:
fac 10 |> printfn "%A" // prints 3628800
fib 10 |> printfn "%A" // prints 55
0 // return an integer exit code</
{{output}}
<pre>3628800
Line 2,752:
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
Line 2,791:
fibs() |> Seq.take 20 |> Seq.iter (printf "%A ")
printfn ""
0 // return an integer exit code</
{{output}}
<pre>3628800
Line 2,798:
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
// the application of this true Y-combinator is the same as for the above non function recursive version.</
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.
Line 2,809:
=={{header|Factor}}==
In rosettacode/Y.factor
<
IN: rosettacode.Y
: Y ( quot -- quot )
Line 2,818:
: almost-fib ( quot -- quot )
'[ dup 2 >= [ 1 2 [ - @ ] bi-curry@ bi + ] when ] ;</
In rosettacode/Y-tests.factor
<
IN: rosettacode.Y.tests
[ 120 ] [ 5 [ almost-fac ] Y call ] unit-test
[ 8 ] [ 6 [ almost-fib ] Y call ] unit-test</
running the tests :
<pre> ( scratchpad - auto ) "rosettacode.Y" test
Line 2,832:
=={{header|Falcon}}==
<syntaxhighlight lang="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) }}
Line 2,842:
> "Factorial 10: ", YFac(10)
> "Fibonacci 10: ", YFib(10)
</syntaxhighlight>
=={{header|Forth}}==
<
variable 'xt
\ Make room for an xt.
Line 2,856:
: y, ( xt1 -- xt2 ) >r :noname @xt, r> compile, postpone ; ;
\ Make a new instance of the Y combinator.
: y ( xt1 -- xt2 ) xt, y, dup !xt ;</
Samples:
<
10 :noname ( u1 xt -- u2 ) over ?dup if 1- swap execute * else 2drop 1 then ;
y execute . 3628800 ok
Line 2,866:
10 :noname ( u1 xt -- u2 ) over 2 < if drop else >r 1- dup r@ execute swap 1- r> execute + then ;
y execute . 55 ok
</syntaxhighlight>
=={{header|FreeBASIC}}==
FreeBASIC does not support nested functions, lambda expressions or functions inside nested types
<
Y = f
End Function
Line 2,906:
test("fac")
test("fib")
Sleep</
{{out}}
<pre>fac: 1 2 6 24 120 720 5040 40320 362880 3628800
Line 2,913:
=={{header|GAP}}==
<
local u;
u := x -> x(x);
Line 2,947:
Y(fac)(8);
# 40320</
=={{header|Genyris}}==
{{trans|Scheme}}
<
function (n)
if (equal? n 0) 1
Line 2,969:
assertEqual ((Y fac) 5) 120
assertEqual ((Y fib) 8) 21</
=={{header|Go}}==
<
import "fmt"
Line 3,012:
return f(x-1)+f(x-2)
}
}</
{{out}}
<pre>
Line 3,020:
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 ->
Line 3,040:
}
assert fib(10) == 55</
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 } }
Line 3,050:
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 }
Line 3,099:
[ 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...
Line 3,150:
, 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).
Line 3,161:
===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')
)
</syntaxhighlight>
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
55</
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
Line 3,181:
gab=. 1 :'u u`:6' NB. The AR of the adverb and the adverb itself as a train
Y=. ara srt gab NB. Train of adverbs</
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
Line 3,198:
8 11 20 41 86 179 368
NB. OEIS A097813 - main diagonal
NB. OEIS A050488 = A097813 - 1 - adyacent upper off-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
Line 3,217:
Fib=. ((u sr n - 2:) + u sr n - 1:) ^: (1 < n)
Fib f. Y 10
55</
The stateless functions are shown next (the f. adverb replaces all embedded names by its referents):
<
'1:`(] * [ ([ 128!:2 ,&<) ] - 1:)@.(0 < ])&>/'&([ 128!:2 ,&<)
Line 3,230:
Fib f. NB. Fibonacci step...
(([ ([ 128!:2 ,&<) ] - 2:) + [ ([ 128!:2 ,&<) ] - 1:)^:(1 < ])</
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)
((((&>)/)((((^:_1)b.)(`_1))(`:6)))(&([ 128!:2 ,&<)))</
===Explicit alternate implementation===
Line 3,243:
Another approach:
<
f=. u Defer
(5!:1<'f') f y
Line 3,262:
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
0 1 1 2 3 5 8 13 21 34</
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
:
Line 3,283:
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.
Line 3,289:
For example:
<
3628800</
=={{header|Java}}==
{{works with|Java|8+}}
<
public interface YCombinator {
Line 3,319:
System.out.println("fac(10) = " + fac.apply(10));
}
}</
{{out}}
<pre>
Line 3,326:
</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) {
Line 3,337:
}
};
}</
{{works with|Java|pre-8}}
We define a generic function interface like Java 8's <code>Function</code>.
<
public B call(A x);
}
Line 3,393:
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
Line 3,404:
return apply(this);
}
}</
<
import java.util.function.UnaryOperator;
@FunctionalInterface
public interface FixedPoint<FUNCTION> extends Function<UnaryOperator<FUNCTION>, FUNCTION> {}</
<
import java.util.Optional;
import java.util.function.Function;
Line 3,454:
return inputs -> apply((INPUTS[]) Arrays.stream(inputs).parallel().map(transformer).toArray());
}
}</
<
import java.math.BigInteger;
import java.util.Arrays;
Line 3,529:
).forEach(System.out::println);
}
}</
{{out}} (may depend on which function gets processed first):
<syntaxhighlight lang="text">factorial[10] = 3628800
ackermann[3, 2] = 29
fibonacci[20] = 6765</
=={{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() {
Line 3,563:
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);
Line 3,573:
});
});
}</
A functionally equivalent version using the implicit <code>this</code> parameter is also possible:
<
return (function(h) {
return h(h);
Line 3,591:
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))))
Line 3,629:
fact=>(n,m=1)=>n<2?m:fact(n-1,n*m);
tailfact= // Tail call version of factorial function
Y(opentailfact);</
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)=>(
Line 3,639:
polyfix(
(even,odd)=>n=>(n===0)||odd(n-1),
(even,odd)=>n=>(n!==0)&&even(n-1));</
A minimalist version:
<
var fac = Y(f => n => n > 1 ? n * f(n-1) : 1);</
=={{header|Joy}}==
<syntaxhighlight lang=
fac == [[pop null] [pop succ] [[dup pred] dip i *] ifte] y.</syntaxhighlight>
=={{header|Julia}}==
<
_
_ _ _(_)_ | Documentation: https://docs.julialang.org
Line 3,670:
Y = f -> (x -> x(x))(y -> f((t...) -> y(y)(t...)))
Y
</syntaxhighlight>
Usage:
<
julia> fac = f -> (n -> n < 2 ? 1 : n * f(n - 1))
#9 (generic function with 1 method)
Line 3,706:
34
55
</syntaxhighlight>
=={{header|Kitten}}==
<
-> f; { f y } f call
Line 3,728:
5 \fac y say // 120
10 \fib y say // 55
</syntaxhighlight>
=={{header|Klingphix}}==
<syntaxhighlight lang="klingphix">:fac
dup 1 great [dup 1 sub fac mult] if
;
Line 3,751:
@fac "fac" test
"End " input</
{{out}}
<pre>fib: 1 1 2 3 5 8 13 21 34 55
Line 3,758:
=={{header|Kotlin}}==
<
typealias Func<T, R> = (T) -> R
Line 3,779:
for (i in 1..10) print("${y(::fib)(i)} ")
println()
}</
{{out}}
Line 3,790:
Tested in http://lambdaway.free.fr/lambdawalks/?view=Ycombinator
<syntaxhighlight lang="scheme">
1) defining the Ycombinator
{def Y {lambda {:f} {:f :f}}}
Line 3,815:
-> 34
</syntaxhighlight>
=={{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
</syntaxhighlight>
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)
print(factorial(7))</
=={{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.
<syntaxhighlight lang="m2000 interpreter">
Module Ycombinator {
\\ y() return value. no use of closure
Line 3,849:
}
Ycombinator
</syntaxhighlight>
<syntaxhighlight lang="m2000 interpreter">
Module Checkit {
Rem {
Line 3,886:
}
CheckRecursion
</syntaxhighlight>
=={{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:
<syntaxhighlight lang="manool">
{ {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
Line 3,902:
}
}
</syntaxhighlight>
Using less syntactic sugar:
<syntaxhighlight lang="manool">
{ {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
Line 3,916:
}
}
</syntaxhighlight>
{{output}}
<pre>
Line 3,942:
=={{header|Maple}}==
<syntaxhighlight lang="maple">
> Y:=f->(x->x(x))(g->f((()->g(g)(args)))):
> Yfac:=Y(f->(x->`if`(x<2,1,x*f(x-1)))):
Line 3,950:
> seq( Yfib( i ), i = 1 .. 10 );
1, 1, 2, 3, 5, 8, 13, 21, 34, 55
</syntaxhighlight>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
factorial = Y[Function[f, If[# < 1, 1, # f[# - 1]] &]];
fibonacci = Y[Function[f, If[# < 2, #, f[# - 1] + f[# - 2]] &]];</
=={{header|Moonscript}}==
<
factorial = Z (f using nil) -> (n) -> if n == 0 then 1 else n * f n - 1</
=={{header|Nim}}==
<
# Z-combinators differ from Y-combinators in lacking one Beta reduction of
# the extra `T` argument to the function to be recursed...
Line 4,034:
let fibs = fibsy
for _ in 1 .. 20: stdout.write fibs(), " "
echo()</
{{out}}
<pre>3628800
Line 4,048:
=={{header|Objective-C}}==
{{works with|Mac OS X|10.6+}}{{works with|iOS|4.0+}}
<
typedef int (^Func)(int);
Line 4,088:
}
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;;
Line 4,129:
fix fib 8;;
(* - : int = 21 *)</
The usual version using recursion, disallowed by the task:
<
=={{header|Oforth}}==
Line 4,138:
With recursion into Y definition (so non stateless Y) :
<
Without recursion into Y definition (stateless Y).
<
: Y(f) #X f X ;</
Usage :
<
#almost-fact Y => fact
Line 4,155:
n 0 == ifTrue: [ 1 m 1 - f perform return ]
n 1 - m f perform m 1 - f perform ;
#almost-Ackermann Y => Ackermann </
=={{header|Order}}==
<
#define ORDER_PP_DEF_8y \
Line 4,176:
ORDER_PP(8to_lit(8ap(8y(8fac), 10))) // 3628800
ORDER_PP(8ap(8y(8fib), 10)) // 55</
=={{header|Oz}}==
<
Y = fun {$ F}
{fun {$ X} {X X} end
Line 4,201:
in
{Show {Fac 5}}
{Show {Fib 8}}</
=={{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])
apply(fib, [1..10])</
{{out}}
<pre>%1 = [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
Line 4,215:
=={{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
Line 4,228:
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
Line 4,234:
The usual version using recursion, disallowed by the task:
<
sub {$f->(Y($f))->(@_)}
}</
=={{header|Phix}}==
Line 4,249:
[[Partial_function_application#Phix|Partial_function_application]],
and/or [[Function_composition#Phix|Function_composition]]
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">call_fn</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
Line 4,277:
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"fac"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"fib"</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 4,285:
=={{header|Phixmonti}}==
<
def fac
Line 4,309:
getid fac "fac" test
getid fib "fib" test</
=={{header|PHP}}==
{{works with|PHP|5.3+}}
<
function Y($f) {
$g = function($w) use($f) {
Line 4,334:
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).';
Line 4,369:
$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) {
Line 4,392:
});
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)))))
(X X) ) )</
===Factorial===
<
(de fact (F)
(curry (F) (N)
Line 4,409:
: ((Y fact) 6)
-> 720</
===Fibonacci sequence===
<
(de fibo (F)
(curry (F) (N)
Line 4,420:
: ((Y fibo) 22)
-> 28657</
===Ackermann function===
<
(de ack (F)
(curry (F) (X Y)
Line 4,432:
: ((Y ack) 3 4)
-> 125</
=={{header|Pop11}}==
<
procedure (x); x(x) endprocedure(
procedure (y);
Line 4,456:
Y(fac)(5) =>
Y(fib)(5) =></
{{out}}
<pre>
Line 4,466:
{{trans|Joy}}
{{libheader|initlib}}
<
{dup cons} exch concat dup cons i
}.
Line 4,473:
{ {pop zero?} {pop succ} {{dup pred} dip i *} ifte }
y
}.</
=={{header|PowerShell}}==
Line 4,484:
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 @"
Line 4,534:
$Z.InvokeReturnAsIs($fac).InvokeReturnAsIs(5)
$Z.InvokeReturnAsIs($fib).InvokeReturnAsIs(5)</
GetNewClosure() was added in Powershell 2, allowing for an implementation without metaprogramming. The following was tested with Powershell 4.
<
param ($f)
Line 4,586:
$Y.invoke($fact).invoke(5)
$Y.invoke($fib).invoke(5)</
=={{header|Prolog}}==
Line 4,593:
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
Line 4,624:
),
y(Fact, 10, FF), format('Fact(~w) = ~w~n', [10, FF]).</
{{out}}
<pre>
Line 4,633:
=={{header|Python}}==
<
>>> fac = lambda f: lambda n: (1 if n<2 else n*f(n-1))
>>> [ Y(fac)(i) for i in range(10) ]
Line 4,639:
>>> 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]</
The usual version using recursion, disallowed by the task:
<
<
=={{header|Q}}==
<
> fac: {{$[y<2; 1; y*x y-1]} x}
> (Y fac) 6
Line 4,654:
> (Y fib) each til 20
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
</syntaxhighlight>
=={{header|Quackery}}==
Line 4,668:
Without the restriction on self referencing, <code>recursive</code> could be defined as <code>[ ' [ this ] swap nested join ]</code>.
<
' share nested join
swap nested join
Line 4,682:
say "8 factorial = " 8 ' factorial recursive do echo cr
say "8 fibonacci = " 8 ' fibonacci recursive do echo cr</
{{out}}
Line 4,691:
=={{header|R}}==
<
(function(x) { (x)(x) })( function(y) { f( (function(a) {y(y)})(a) ) } )
}</
<
function(n) {
if (n<2)
Line 4,711:
f(n-1) + f(n-2)
}
}</
<
for(i in 1:9) print(Y(fib)(i))</
=={{header|Racket}}==
The lazy implementation
<
(define Y (λ (f) ((λ (x) (f (x x))) (λ (x) (f (x x))))))
Line 4,726:
(Y (λ (fact) (λ (n) (if (zero? n) 1 (* n (fact (- n 1))))))))
(define Fib
(Y (λ (fib) (λ (n) (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2))))))))</
{{out}}
Line 4,737:
Strict realization:
<
(define Y (λ (b) ((λ (f) (b (λ (x) ((f f) x))))
(λ (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)))
Line 4,760:
(* n (fact (- n 1))))))))
(fact 5)</
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
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) } }
say map Y($_), ^10 for &fac, &fib;</
{{out}}
<pre>(1 1 2 6 24 120 720 5040 40320 362880)
Line 4,774:
Note that Raku doesn't actually need a Y combinator because you can name anonymous functions from the inside:
<syntaxhighlight lang="raku"
=={{header|REBOL}}==
<
;usage example
<
fact: Y :fact*</
=={{header|REXX}}==
Programming note: '''length''', '''reverse''', '''sign''', '''trunc''', '''b2x''', '''d2x''', and '''x2d''' are REXX BIFs ('''B'''uilt '''I'''n '''F'''unctions).
<
numeric digits 1000 /*allow big numbers. */
say ' fib' Y(fib (50) ) /*Fibonacci series. */
Line 4,810:
tfact: procedure; parse arg x; != 1; do j=x to 2 by -3; != !*j; end; return !
qfact: procedure; parse arg x; != 1; do j=x to 2 by -4; != !*j; end; return !
fact: procedure; parse arg x; != 1; do j=2 to x ; != !*j; end; return !</
{{out|output|text= when using the internal default input:}}
<pre>
Line 4,832:
Using a lambda:
<
lambda {|g| g[g]}[lambda do |g|
f[lambda {|*args| g[g][*args]}]
Line 4,842:
fib = lambda{|f| lambda{|n| n < 2 ? n : f[n-1] + f[n-2]}}
p Array.new(10) {|i| y[fib][i]} #=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</
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) } }
Line 4,854:
fib = ->(f) { ->(n) { n < 2 ? n : f.(n-2) + f.(n-1) } }
p 10.times.map {|i| y.(fib).(i)}</
Using a method:
{{works with|Ruby|1.9}}
<
lambda do |g|
f.call {|*args| g[g][*args]}
Line 4,871:
# => [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
p Array.new(10) {|i| fib[i]}
# => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</
The usual version using recursion, disallowed by the task:
<
lambda {|*args| f[y[f]][*args]}
end</
=={{header|Rust}}==
{{works with|Rust|1.44.1 stable}}
<
//! A simple implementation of the Y Combinator:
//! λf.(λx.xx)(λx.f(xx))
Line 4,936:
}
</syntaxhighlight>
{{output}}
<pre>
Line 4,945:
=={{header|Scala}}==
Credit goes to the thread in [https://web.archive.org/web/20160709050901/http://scala-blogs.org/2008/09/y-combinator-in-scala.html scala blog]
<
def Y[A, B](f: (A => B) => (A => B)): A => B = {
case class W(wf: W => (A => B)) {
Line 4,953:
g(W(g))
}
</syntaxhighlight>
Example
<
val fac: Int => Int = Y[Int, Int](f => i => if (i <= 0) 1 else f(i - 1) * i)
fac(6) //> res0: Int = 720
Line 4,961:
val fib: Int => Int = Y[Int, Int](f => i => if (i < 2) i else f(i - 1) + f(i - 2))
fib(6) //> res1: Int = 8
</syntaxhighlight>
=={{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)))
Line 5,010:
(display (fib2 134))
(newline)</
{{out}}
<pre>720
Line 5,017:
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)
(f (lambda a (apply (Yr f) a)))))</
And another way is:
<
(lambda (f)
(lambda a (apply (f (Y2r f)) a))))</
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)
(lambda a (apply (f (g g)) a))))))</
=={{header|Shen}}==
<
F -> ((/. X (X X))
(/. X (F (/. Z ((X X) Z))))))
Line 5,044:
(Fac 0)
(Fac 5)
(Fac 10)))</
{{out}}
<pre>1
Line 5,051:
=={{header|Sidef}}==
<
var fac = ->(f) { ->(n) { n < 2 ? 1 : (n * f(n-1)) } }
Line 5,057:
var fib = ->(f) { ->(n) { n < 2 ? n : (f(n-2) + f(n-1)) } }
say 10.of { |i| y(fib)(i) }</
{{out}}
<pre>
Line 5,066:
=={{header|Slate}}==
The Y combinator is already defined in slate as:
<
[[| :f | [| :x | f applyWith: (x applyWith: x)]
applyWith: [| :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)] ] ].
Line 5,080:
fact := Y value: [:f| [:i| i = 0 ifTrue: [1] ifFalse: [(f value: i-1) * i] ] ].
(fact value: 10) displayNl.</
{{out}}
<pre>55
Line 5,086:
The usual version using recursion, disallowed by the task:
<
=={{header|Standard ML}}==
<
fun unroll (Roll x) = x
Line 5,109:
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</
The usual version using recursion, disallowed by the task:
<
=={{header|SuperCollider}}==
Like Ruby, SuperCollider needs an extra level of lambda-abstraction to implement the y-combinator. The z-combinator is straightforward:
<
(
z = { |f|
Line 5,157:
</syntaxhighlight>
=={{header|Swift}}==
Using a recursive type:
<
let o : RecursiveFunc<F> -> F
}
Line 5,177:
}
println("fac(5) = \(fac(5))")
println("fib(9) = \(fib(9))")</
{{out}}
<pre>
Line 5,186:
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
Line 5,231:
5 -> fibonacci -> 'fibonacci 5: $;
' -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 5,244:
This prints out 24, the factorial of 4:
<
(defun y (f)
[(op @1 @1)
Line 5,256:
;; Test:
(format t "~s\n" [[y fac] 4])</
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>.
The compounded <code>@@...</code> notation allows for inner functions to refer to outer parameters, when the notation is nested. Consider <
=={{header|Ursala}}==
The standard y combinator doesn't work in Ursala due to eager
evaluation, but an alternative is easily defined as shown
<
my_fix "h" = r ("f","x"). ("h" r "f") "x"</
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
Line 5,276:
quotes signify a dummy variable. Using this
method, the definition of the factorial function becomes
<
fact = my_fix "f". ~&?\1! product^/~& "f"+ predecessor</
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,
<syntaxhighlight lang
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>
Line 5,295:
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.
<
examples = (fact* <1,2,3,4,5,6,7,8>,fib* <1,2,3,4,5,6,7,8>)</
{{out}}
<pre>
Line 5,312:
(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
my_fix "h" = "h" my_fix "h"</
Note that this equation is solved using the next fixed point combinator in the hierarchy.
Line 5,322:
{{trans|Phix}}
The IIf as translation of Iff can not be used as IIf executes both true and false parts and will cause a stack overflow.
<
call_fn = Application.Run(f, f, n)
End Function
Line 5,359:
test "fac"
test "fib"
End Sub</
<pre>fac
1 2 6 24 120 720 5040 40320 362880 3628800
Line 5,366:
=={{header|Verbexx}}==
<
y @FN [f]
Line 5,400:
@LOOP init:{ i = -1} while:(i <= 16) next:{i++}
{ @SAY "fibonacci<" i "> =" (@fibonacci 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)
Line 5,426:
echo Callx(Callx(g:Y, [g:fac]), [5])
echo map(range(10), 'Callx(Callx(Y, [fac]), [v:val])')
</syntaxhighlight>
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'
Line 5,438:
echo Y(Fac)(5)
echo map(range(10), 'Y(Fac)(v:val)')
</syntaxhighlight>
Output:
<pre>120
Line 5,444:
=={{header|Wart}}==
<
def (Y improver)
((fn(gen) gen.gen)
Line 5,457:
(n * (f n-1))))))
prn factorial.5</
{{omit from|ACL2}}
Line 5,466:
=={{header|Wren}}==
{{trans|Go}}
<
var g = Fn.new { |r| f.call { |x| r.call(r).call(x) } }
return g.call(g)
Line 5,479:
System.print("fac(10) = %(fac.call(10))")
System.print("fib(10) = %(fib.call(10))")</
{{out}}
Line 5,491:
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)}) ) } )
}
Line 5,500:
$fib(6)
)
</syntaxhighlight>
{{out}}
<syntaxhighlight lang
=={{header|Yabasic}}==
<
if n > 1 then
return n * execute(self$, self$, n - 1)
Line 5,532:
test("fac")
test("fib")</
=={{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();
[0..10].apply(Y(almost_factorial)).println();</
{{out}}
<pre>
Line 5,545:
L(1,1,2,6,24,120,720,5040,40320,362880,3628800)
</pre>
<
Y(almost_fib)(9).println();
[0..10].apply(Y(almost_fib)).println();</
{{out}}
<pre>
|