Last active
May 15, 2023 10:19
-
-
Save hickford/ed6dc83b0bb7ea6c3287792f88f59576 to your computer and use it in GitHub Desktop.
Y combinator in F# and C#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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" |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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