How to resolve the algorithm Y combinator step by step in the C# programming language

Published on 12 May 2024 09:40 PM
#C_Sharp

How to resolve the algorithm Y combinator step by step in the C# programming language

Table of Contents

Problem Statement

In strict functional programming and the lambda calculus, functions (lambda expressions) don't have state and are only allowed to refer to arguments of enclosing functions. This rules out the usual definition of a recursive function wherein a function is associated with the state of a variable and this variable's state is used in the body of the function. The   Y combinator   is itself a stateless function that, when applied to another stateless function, returns a recursive version of the function. The Y combinator is the simplest of the class of such functions, called fixed-point combinators.

Define the stateless   Y combinator   and use it to compute factorials and Fibonacci numbers from other stateless functions or lambda expressions.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Y combinator step by step in the C# programming language

The Y combinator is a function that takes a function as input and returns a fixed point of that function. A fixed point of a function is a value that, when passed to the function, returns itself.

In C#, the Y combinator can be implemented as follows:

static class YCombinator
{
   public static Func<Func<T, TResult>, Func<T, TResult>> Fix { get; } =
       f => ((RecursiveFunc<T, TResult>)(g => f(x => g(g)(x))))(g => f(x => g(g)(x)));
}

Here, Func<T, TResult> is a function that takes a value of type T as input and returns a value of type TResult. The Fix function takes a function of type Func<T, TResult> as input and returns a fixed point of that function.

The RecursiveFunc delegate is a delegate that takes a function of type RecursiveFunc<T, TResult> as input and returns a value of type TResult. The g parameter of the RecursiveFunc delegate is a fixed point of the function that is passed to the Fix function.

The Fix function is implemented using a technique called "self-application." The function g is applied to itself twice, and the result of the second application is returned. This ensures that g is a fixed point of the function that is passed to the Fix function.

The Y combinator can be used to implement a variety of recursive functions. For example, the following code uses the Y combinator to implement the factorial function:

static class Program
{
   static void Main()
   {
       var fac = YCombinator<int, int>.Fix(f => x => x < 2 ? 1 : x * f(x - 1));
       var fib = YCombinator<int, int>.Fix(f => x => x < 2 ? x : f(x - 1) + f(x - 2));

       Console.WriteLine(fac(10));
       Console.WriteLine(fib(10));
   }
}

The output of this program is:

362880
55

Source code in the csharp programming language

using System;

static class YCombinator<T, TResult>
{
    // RecursiveFunc is not needed to call Fix() and so can be private.
    private delegate Func<T, TResult> RecursiveFunc(RecursiveFunc r);

    public static Func<Func<Func<T, TResult>, Func<T, TResult>>, Func<T, TResult>> Fix { get; } =
        f => ((RecursiveFunc)(g => f(x => g(g)(x))))(g => f(x => g(g)(x)));
}

static class Program
{
    static void Main()
    {
        var fac = YCombinator<int, int>.Fix(f => x => x < 2 ? 1 : x * f(x - 1));
        var fib = YCombinator<int, int>.Fix(f => x => x < 2 ? x : f(x - 1) + f(x - 2));

        Console.WriteLine(fac(10));
        Console.WriteLine(fib(10));
    }
}


static class YCombinator
{
    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)));
}


static class YCombinator<T, TResult>
{
    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))));
}


static class YCombinator
{
    static Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f) => x => f(Fix(f))(x);
}


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

static class Program {
    struct RecursiveFunc<F> {
        public System.Func<RecursiveFunc<F>, F> o;
    }

    static System.Func<A, B> Y<A, B>(System.Func<System.Func<A, B>, System.Func<A, B>> f) {
        var r = new RecursiveFunc<System.Func<A, B>>() {
            o = new System.Func<RecursiveFunc<System.Func<A, B>>, System.Func<A, B>>((RecursiveFunc<System.Func<A, B>> w) => {
                return f(new System.Func<A, B>((A x) => {
                    return w.o(w)(x);
                }));
            })
        };
        return r.o(r);
    }

    static FuncFunc almost_fac = (Func f) => {
        return new Func((int n) => {
            if (n <= 1) return 1;
            return n * f(n - 1);
        });
    };

    static FuncFunc almost_fib = (Func f) => {
        return new Func((int n) => {
            if (n <= 2) return 1;
            return f(n - 1) + f(n - 2);
        });
    };

    static int Main() {
        var fib = Y(almost_fib);
        var fac = Y(almost_fac);
        System.Console.WriteLine("fib(10) = " + fib(10));
        System.Console.WriteLine("fac(10) = " + fac(10));
        return 0;
    }
}


using System;

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

static class Program {
    struct RecursiveFunc<F> {
        public Func<RecursiveFunc<F>, F> o;
    }

    static Func<A, B> Y<A, B>(Func<Func<A, B>, Func<A, B>> f) {
        var r = new RecursiveFunc<Func<A, B>> {
            o = w => f(x => w.o(w)(x))
        };
        return r.o(r);
    }

    static FuncFunc almost_fac = f => n => n <= 1 ? 1 : n * f(n - 1);

    static FuncFunc almost_fib = f => n => n <= 2 ? 1 : f(n - 1) + f(n - 2);

    static void Main() {
        var fib = Y(almost_fib);
        var fac = Y(almost_fac);
        Console.WriteLine("fib(10) = " + fib(10));
        Console.WriteLine("fac(10) = " + fac(10));
    }
}


using System;
using System.Diagnostics;

class Program {
    public delegate TResult ParamsFunc<T, TResult>(params T[] args);

    static class Y<Result, Args> {
        class RecursiveFunction {
            public Func<RecursiveFunction, ParamsFunc<Args, Result>> o;
            public RecursiveFunction(Func<RecursiveFunction, ParamsFunc<Args, Result>> o) => this.o = o;
        }

        public static ParamsFunc<Args, Result> y1(
                Func<ParamsFunc<Args, Result>, ParamsFunc<Args, Result>> f) {

            var r = new RecursiveFunction((RecursiveFunction w)
                => f((Args[] args) => w.o(w)(args)));

            return r.o(r);
        }
    }

    static ParamsFunc<Args, Result> y2<Args, Result>(
            Func<ParamsFunc<Args, Result>, ParamsFunc<Args, Result>> f) {

        Func<dynamic, ParamsFunc<Args, Result>> r = w => {
            Debug.Assert(w is Func<dynamic, ParamsFunc<Args, Result>>);
            return f((Args[] args) => w(w)(args));
        };

        return r(r);
    }

    static ParamsFunc<Args, Result> y3<Args, Result>(
            Func<ParamsFunc<Args, Result>, ParamsFunc<Args, Result>> f)
        => (Args[] args) => f(y3(f))(args);

    static void Main() {
        var factorialY1 = Y<int, int>.y1((ParamsFunc<int, int> fact) => (int[] x)
            => (x[0] > 1) ? x[0] * fact(x[0] - 1) : 1);

        var fibY1 = Y<int, int>.y1((ParamsFunc<int, int> fib) => (int[] x)
            => (x[0] > 2) ? fib(x[0] - 1) + fib(x[0] - 2) : 2);

        Console.WriteLine(factorialY1(10)); // 362880
        Console.WriteLine(fibY1(10));       // 110
    }
}


using System;
using System.Diagnostics;

static class Program {
    delegate TResult ParamsFunc<T, TResult>(params T[] args);

    static class Y<Result, Args> {
        class RecursiveFunction {
            public Func<RecursiveFunction, ParamsFunc<Args, Result>> o;
            public RecursiveFunction(Func<RecursiveFunction, ParamsFunc<Args, Result>> o) => this.o = o;
        }

        public static ParamsFunc<Args, Result> y1(
                Func<ParamsFunc<Args, Result>, ParamsFunc<Args, Result>> f) {

            var r = new RecursiveFunction(w => f(args => w.o(w)(args)));

            return r.o(r);
        }
    }

    static ParamsFunc<Args, Result> y2<Args, Result>(
            Func<ParamsFunc<Args, Result>, ParamsFunc<Args, Result>> f) {

        Func<dynamic, ParamsFunc<Args, Result>> r = w => {
            Debug.Assert(w is Func<dynamic, ParamsFunc<Args, Result>>);
            return f(args => w(w)(args));
        };

        return r(r);
    }

    static ParamsFunc<Args, Result> y3<Args, Result>(
            Func<ParamsFunc<Args, Result>, ParamsFunc<Args, Result>> f)
        => args => f(y3(f))(args);

    static void Main() {
        var factorialY1 = Y<int, int>.y1(fact => x => (x[0] > 1) ? x[0] * fact(x[0] - 1) : 1);
        var fibY1 = Y<int, int>.y1(fib => x => (x[0] > 2) ? fib(x[0] - 1) + fib(x[0] - 2) : 2);

        Console.WriteLine(factorialY1(10));
        Console.WriteLine(fibY1(10));
    }
}


using System;

// 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.
using Func = System.Func<int, int>;
using FuncFunc = System.Func<System.Func<int, int>, System.Func<int, int>>;

delegate Func RecursiveFunc(RecursiveFunc f);

static class Program {
    static void Main() {
        var fac = Y(almost_fac);
        var fib = Y(almost_fib);
        Console.WriteLine("fac(10) = " + fac(10));
        Console.WriteLine("fib(10) = " + fib(10));
    }

    static Func Y(FuncFunc f) {
        RecursiveFunc g = delegate (RecursiveFunc r) {
            return f(delegate (int x) {
                return r(r)(x);
            });
        };
        return g(g);
    }

    static Func almost_fac(Func f) {
        return delegate (int x) {
            if (x <= 1) {
                return 1;
            }
            return x * f(x-1);
        };
    }

    static Func almost_fib(Func f) {
        return delegate (int x) {
            if (x <= 2) {
                return 1;
            }
            return f(x-1)+f(x-2);
        };
    }
}


    static Func Y(FuncFunc f) {
        return delegate (int x) {
            return f(Y(f))(x);
        };
    }


using System;

delegate int Func(int i);
delegate Func FuncFunc(Func f);
delegate Func RecursiveFunc(RecursiveFunc f);

static class Program {
    static void Main() {
        var fac = Y(almost_fac);
        var fib = Y(almost_fib);
        Console.WriteLine("fac(10) = " + fac(10));
        Console.WriteLine("fib(10) = " + fib(10));
    }

    static Func Y(FuncFunc f) {
        RecursiveFunc g = r => f(x => r(r)(x));
        return g(g);
    }

    static Func almost_fac(Func f) => x => x <= 1 ? 1 : x * f(x - 1);

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


    static Func Y(FuncFunc f) => x => f(Y(f))(x);


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


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(params 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));
    }
}


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(params 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));
    }
}


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


using System;

static class Program {
    struct RecursiveFunc<F> {
        public Func<RecursiveFunc<F>, F> o;
    }

    static Func<A, B> Y<A, B>(Func<Func<A, B>, Func<A, B>> f) {
        var r = new RecursiveFunc<Func<A, B>> { o = w => f(_0 => w.o(w)(_0)) };
        return r.o(r);
    }

    static void Main() {
        // C# can't infer the type arguments to Y either; either it or f must be explicitly typed.
        var fac = Y((Func<int, int> f) => _0 => _0 <= 1 ? 1 : _0 * f(_0 - 1));
        var fib = Y((Func<int, int> f) => _0 => _0 <= 2 ? 1 : f(_0 - 1) + f(_0 - 2));

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


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


    public static Func<In, Out> Y<In, Out>(Func<Func<In, Out>, Func<In, Out>> f) {
        return x => f(Y(f))(x);
    }

You may also check:How to resolve the algorithm Averages/Median step by step in the Groovy programming language
You may also check:How to resolve the algorithm Vigenère cipher step by step in the PowerShell programming language
You may also check:How to resolve the algorithm Sorting algorithms/Pancake sort step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Ternary logic step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Empty string step by step in the Diego programming language