Skip to content

Instantly share code, notes, and snippets.

@hickford
Last active May 15, 2023 10:19
Show Gist options
  • Save hickford/ed6dc83b0bb7ea6c3287792f88f59576 to your computer and use it in GitHub Desktop.
Save hickford/ed6dc83b0bb7ea6c3287792f88f59576 to your computer and use it in GitHub Desktop.
Y combinator in F# and C#
let protoFib f x = if x > 1 then f(x-1) + f(x-2) else x
let rec Y f x = f (Y f) x
let fib = Y protoFib
[1..10] |> List.map fib |> printfn "%A"
void Main()
{
Fib(10).Dump();
}
int Fib(int n)
{
return Y<int,int>(ProtoFib, n);
}
// attempt at Fibonacci function
int ProtoFib(Func<int,int> f, int x) {
return x > 1 ? f(x-1) + f(x-2) : x;
}
// attempt at factorial function
double ProtoFactorial(Func<int, double> f, int x)
{
return x > 1 ? x * f(x-1) : 1;
}
U Y<T,U>(Func<Func<T, U>, T, U> f, T x) {
var Yf = new Func<T, U>(t => Y(f, t));
return f(Yf, x);
}
void Main()
{
var Fib = Y<int,int>(ProtoFib);
Fib(10).Dump();
}
int ProtoFib(Func<int,int> f, int x) {
return x > 1 ? f(x-1) + f(x-2) : x;
}
Func<T,U> Y<T,U>(Func<Func<T, U>, T, U> f) {
var Yf = new Func<T, U>(t => Y(f)(t));
return new Func<T,U>(x => f(Yf, x));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment