Skip to content

Instantly share code, notes, and snippets.

@savaged
Created March 25, 2023 19:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save savaged/bdb738c3c8a300d8a3a22f1fe0a97159 to your computer and use it in GitHub Desktop.
Save savaged/bdb738c3c8a300d8a3a22f1fe0a97159 to your computer and use it in GitHub Desktop.
Trying to get my head around the y combinator
// Y = λf.(λx.f(x x))(λx.f(x x))
var factorial = YCombinator.Y<int, int>(recursiveFunc => num => num == 0 ? 1 : num * recursiveFunc(num - 1));
var fibonacci = YCombinator.Y<int, int>(recursiveFunc => num => num <= 1 ? 1 : recursiveFunc(num - 1) + recursiveFunc(num - 2));
// Test with sample inputs
Console.WriteLine(factorial(3));
Console.WriteLine(fibonacci(5));
// Implementation of Y combinator
static class YCombinator
{
// Define delegate for self-referential function
public delegate T SelfReferentialFunc<T>(SelfReferentialFunc<T> s);
// Define a function that applies a self-referential function to itself
public static T Apply<T>(SelfReferentialFunc<T> s) => s(s);
// Define Y combinator function
public static Func<A, Z> Y<A, Z>(Func<Func<A, Z>, Func<A, Z>> f) =>
Apply<Func<A, Z>>(r => a => f(Apply(r))(a));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment