Anonymous user
Y combinator: Difference between revisions
→{{header|C sharp}}: Added translations of Java
(→{{header|C sharp}}: Added translation of Swift) |
(→{{header|C sharp}}: Added translations of Java) |
||
Line 1,100:
Recursive:
<lang csharp> static Func Y(FuncFunc f) => x => f(Y(f))(x);</lang>
====[http://rosettacode.org/mw/index.php?oldid=287744#Java Java]====
'''Verbatim'''
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.
<lang csharp>using System;
static class Program {
interface Function<T, R> {
R apply(T t);
}
interface RecursiveFunction<F> : Function<RecursiveFunction<F>, F> {
}
static class Functions {
class Function<T, R> : Program.Function<T, R> {
readonly Func<T, R> _inner;
public Function(Func<T, R> inner) => this._inner = inner;
public R apply(T t) => this._inner(t);
}
class RecursiveFunction<F> : Function<Program.RecursiveFunction<F>, F>, Program.RecursiveFunction<F> {
public RecursiveFunction(Func<Program.RecursiveFunction<F>, F> inner) : base(inner) {
}
}
public static Program.Function<T, R> Create<T, R>(Func<T, R> inner) => new Function<T, R>(inner);
public static Program.RecursiveFunction<F> Create<F>(Func<Program.RecursiveFunction<F>, F> inner) => new RecursiveFunction<F>(inner);
}
static Function<A, B> Y<A, B>(Function<Function<A, B>, Function<A, B>> f) {
var r = Functions.Create<Function<A, B>>(w => f.apply(Functions.Create<A, B>(x => w.apply(w).apply(x))));
return r.apply(r);
}
static void Main(params String[] arguments) {
Function<int, int> fib = Y(Functions.Create<Function<int, int>, Function<int, int>>(f => Functions.Create<int, int>(n =>
(n <= 2)
? 1
: (f.apply(n - 1) + f.apply(n - 2))))
);
Function<int, int> fac = Y(Functions.Create<Function<int, int>, Function<int, int>>(f => Functions.Create<int, int>(n =>
(n <= 1)
? 1
: (n * f.apply(n - 1))))
);
Console.WriteLine("fib(10) = " + fib.apply(10));
Console.WriteLine("fac(10) = " + fac.apply(10));
}
}</lang>
'''"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].
<lang csharp>using System;
static class YCombinator {
interface Function<T, R> {
R apply(T t);
}
interface RecursiveFunction<F> : Function<RecursiveFunction<F>, F> {
}
static class Y<A, B> {
class __1 : RecursiveFunction<Function<A, B>> {
class __2 : Function<A, B> {
readonly RecursiveFunction<Function<A, B>> w;
public __2(RecursiveFunction<Function<A, B>> w) {
this.w = w;
}
public B apply(A x) {
return w.apply(w).apply(x);
}
}
Function<Function<A, B>, Function<A, B>> f;
public __1(Function<Function<A, B>, Function<A, B>> f) {
this.f = f;
}
public Function<A, B> apply(RecursiveFunction<Function<A, B>> w) {
return f.apply(new __2(w));
}
}
public static Function<A, B> _(Function<Function<A, B>, Function<A, B>> f) {
var r = new __1(f);
return r.apply(r);
}
}
class __1 : Function<Function<int, int>, Function<int, int>> {
class __2 : Function<int, int> {
readonly Function<int, int> f;
public __2(Function<int, int> f) {
this.f = f;
}
public int apply(int n) {
return
(n <= 2)
? 1
: (f.apply(n - 1) + f.apply(n - 2));
}
}
public Function<int, int> apply(Function<int, int> f) {
return new __2(f);
}
}
class __2 : Function<Function<int, int>, Function<int, int>> {
class __3 : Function<int, int> {
readonly Function<int, int> f;
public __3(Function<int, int> f) {
this.f = f;
}
public int apply(int n) {
return
(n <= 1)
? 1
: (n * f.apply(n - 1));
}
}
public Function<int, int> apply(Function<int, int> f) {
return new __3(f);
}
}
static void Main(string[] arguments) {
Function<int, int> fib = Y<int, int>._(new __1());
Function<int, int> fac = Y<int, int>._(new __2());
Console.WriteLine("fib(10) = " + fib.apply(10));
Console.WriteLine("fac(10) = " + fac.apply(10));
}
}</lang>
'''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.
<lang csharp>using System;
class Program {
interface Func {
int apply(int i);
}
interface FuncFunc {
Func apply(Func f);
}
interface RecursiveFunc {
Func apply(RecursiveFunc f);
}
class Y {
class __1 : RecursiveFunc {
class __2 : Func {
readonly RecursiveFunc w;
public __2(RecursiveFunc w) {
this.w = w;
}
public int apply(int x) {
return w.apply(w).apply(x);
}
}
readonly FuncFunc f;
public __1(FuncFunc f) {
this.f = f;
}
public Func apply(RecursiveFunc w) {
return f.apply(new __2(w));
}
}
public static Func _(FuncFunc f) {
__1 r = new __1(f);
return r.apply(r);
}
}
class __fib : FuncFunc {
class __1 : Func {
readonly Func f;
public __1(Func f) {
this.f = f;
}
public int apply(int n) {
return
(n <= 2)
? 1
: (f.apply(n - 1) + f.apply(n - 2));
}
}
public Func apply(Func f) {
return new __1(f);
}
}
class __fac : FuncFunc {
class __1 : Func {
readonly Func f;
public __1(Func f) {
this.f = f;
}
public int apply(int n) {
return
(n <= 1)
? 1
: (n * f.apply(n - 1));
}
}
public Func apply(Func f) {
return new __1(f);
}
}
static void Main(string[] arguments) {
Func fib = Y._(new __fib());
Func fac = Y._(new __fac());
Console.WriteLine("fib(10) = " + fib.apply(10));
Console.WriteLine("fac(10) = " + fac.apply(10));
}
}</lang>
'''Modified/varargs (the last implementation in the Java section)'''
Since C# delegates cannot declare members, extension methods are used to simulate doing so.
<lang csharp>using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
static class Func {
public static Func<T, TResult2> andThen<T, TResult, TResult2>(
this Func<T, TResult> @this,
Func<TResult, TResult2> after)
=> _ => after(@this(_));
}
delegate OUTPUT SelfApplicable<OUTPUT>(SelfApplicable<OUTPUT> s);
static class SelfApplicable {
public static OUTPUT selfApply<OUTPUT>(this SelfApplicable<OUTPUT> @this) => @this(@this);
}
delegate FUNCTION FixedPoint<FUNCTION>(Func<FUNCTION, FUNCTION> f);
delegate OUTPUT VarargsFunction<INPUTS, OUTPUT>(params INPUTS[] inputs);
static class VarargsFunction {
public static VarargsFunction<INPUTS, OUTPUT> from<INPUTS, OUTPUT>(
Func<INPUTS[], OUTPUT> function)
=> function.Invoke;
public static VarargsFunction<INPUTS, OUTPUT> upgrade<INPUTS, OUTPUT>(
Func<INPUTS, OUTPUT> function) {
return inputs => function(inputs[0]);
}
public static VarargsFunction<INPUTS, OUTPUT> upgrade<INPUTS, OUTPUT>(
Func<INPUTS, INPUTS, OUTPUT> function) {
return inputs => function(inputs[0], inputs[1]);
}
public static VarargsFunction<INPUTS, POST_OUTPUT> andThen<INPUTS, OUTPUT, POST_OUTPUT>(
this VarargsFunction<INPUTS, OUTPUT> @this,
VarargsFunction<OUTPUT, POST_OUTPUT> after) {
return inputs => after(@this(inputs));
}
public static Func<INPUTS, OUTPUT> toFunction<INPUTS, OUTPUT>(
this VarargsFunction<INPUTS, OUTPUT> @this) {
return input => @this(input);
}
public static Func<INPUTS, INPUTS, OUTPUT> toBiFunction<INPUTS, OUTPUT>(
this VarargsFunction<INPUTS, OUTPUT> @this) {
return (input, input2) => @this(input, input2);
}
public static VarargsFunction<PRE_INPUTS, OUTPUT> transformArguments<PRE_INPUTS, INPUTS, OUTPUT>(
this VarargsFunction<INPUTS, OUTPUT> @this,
Func<PRE_INPUTS, INPUTS> transformer) {
return inputs => @this(inputs.AsParallel().AsOrdered().Select(transformer).ToArray());
}
}
delegate FixedPoint<FUNCTION> Y<FUNCTION>(SelfApplicable<FixedPoint<FUNCTION>> y);
static class Program {
static TResult Cast<TResult>(this Delegate @this) where TResult : Delegate {
return (TResult)Delegate.CreateDelegate(typeof(TResult), @this.Target, @this.Method);
}
static void Main(params String[] arguments) {
BigInteger TWO = BigInteger.One + BigInteger.One;
Func<IFormattable, long> toLong = x => long.Parse(x.ToString());
Func<IFormattable, BigInteger> toBigInteger = x => new BigInteger(toLong(x));
/* Based on https://gist.github.com/aruld/3965968/#comment-604392 */
Y<VarargsFunction<IFormattable, IFormattable>> combinator = y => f => x => f(y.selfApply()(f))(x);
FixedPoint<VarargsFunction<IFormattable, IFormattable>> fixedPoint =
combinator.Cast<SelfApplicable<FixedPoint<VarargsFunction<IFormattable, IFormattable>>>>().selfApply();
VarargsFunction<IFormattable, IFormattable> fibonacci = fixedPoint(
f => VarargsFunction.upgrade(
toBigInteger.andThen(
n => (IFormattable)(
(n.CompareTo(TWO) <= 0)
? 1
: BigInteger.Parse(f(n - BigInteger.One).ToString())
+ BigInteger.Parse(f(n - TWO).ToString()))
)
)
);
VarargsFunction<IFormattable, IFormattable> factorial = fixedPoint(
f => VarargsFunction.upgrade(
toBigInteger.andThen(
n => (IFormattable)((n.CompareTo(BigInteger.One) <= 0)
? 1
: n * BigInteger.Parse(f(n - BigInteger.One).ToString()))
)
)
);
VarargsFunction<IFormattable, IFormattable> ackermann = fixedPoint(
f => VarargsFunction.upgrade(
(BigInteger m, BigInteger n) => m.Equals(BigInteger.Zero)
? n + BigInteger.One
: f(
m - BigInteger.One,
n.Equals(BigInteger.Zero)
? BigInteger.One
: f(m, n - BigInteger.One)
)
).transformArguments(toBigInteger)
);
var functions = new Dictionary<String, VarargsFunction<IFormattable, IFormattable>>();
functions.Add("fibonacci", fibonacci);
functions.Add("factorial", factorial);
functions.Add("ackermann", ackermann);
var parameters = new Dictionary<VarargsFunction<IFormattable, IFormattable>, IFormattable[]>();
parameters.Add(functions["fibonacci"], new IFormattable[] { 20 });
parameters.Add(functions["factorial"], new IFormattable[] { 10 });
parameters.Add(functions["ackermann"], new IFormattable[] { 3, 2 });
functions.AsParallel().Select(
entry => entry.Key
+ "[" + String.Join(", ", parameters[entry.Value].Select(x => x.ToString())) + "]"
+ " = "
+ entry.Value(parameters[entry.Value])
).ForAll(Console.WriteLine);
}
}</lang>
====[http://rosettacode.org/mw/index.php?oldid=287744#Swift Swift]====
Line 1,105 ⟶ 1,490:
'''Verbatim'''
The more idiomatic version doesn't look much different.
<lang csharp>using System;
| |||