A non-recursive implementation of Y-combinator with memoization in C#

memoizedYcombinator.csx

// non-recursive implementation of Y-combinator, based on example from https://en.wikipedia.org/wiki/Fixed-point_combinator#Type_for_the_Y_combinator
// with memoization


using System;
using System.Diagnostics;
using System.Collections.Concurrent;


//type 'a Recc = In of ('a Recc -> 'a)
//let out (In x) = x
//let yy f = (fun x a -> f(out x x) a)(In(fun x a->f(out x x) a))
class Recc<A> // TODO: can be refactored to a recursive delegate?
{
    public Func<Recc<A>, A> Out { get; }
    public static Recc<A> In<A>(Func<Recc<A>, A> fr) => new Recc<A>(fr);
    Recc(Func<Recc<A>, A> @in) { Out = @in; }
}

// g:(('a -> 'b) Recc -> 'a -> 'b)
Func<A, B> Y<A, B>(Func<Func<A, B>, Func<A, B>> f)
{
    Func<Recc<Func<A, B>>, Func<A, B>> h = x => a => f(x.Out(x))(a);
    return h(Recc<A>.In(h));
}

Func<A, B> YCached<A, B>(Func<Func<A, B>, Func<A, B>> f)
{
    var cache = new ConcurrentDictionary<A, B>();
    Func<Recc<Func<A, B>>, Func<A, B>> h = x => a => cache.GetOrAdd(a, f(x.Out(x)));
    return h(Recc<A>.In(h));
}


// test

Func<long, long> Fib = Y<long, long>(f => x =>
    x <= 1 ? x : f(x - 2) + f(x - 1));

Func<long, long> FibCached =
    YCached<long, long>(f => x =>
        x <= 1 ? x : f(x - 2) + f(x - 1));

static Func<A, B> Timed<A, B>(this Func<A, B> f) =>
    a =>
    {
        var sw = new Stopwatch();
        sw.Restart();
        var b = f(a);
        sw.Stop();
        Console.WriteLine($"Elapsed:{sw.Elapsed}");
        return b;
    };

Timed(Fib)(38) // Elapsed:00:00:13.0030271
  
Timed(FibCached)(38) // Elapsed:00:00:00.0003149