Last active
December 20, 2015 09:19
-
-
Save felipegtx/6106974 to your computer and use it in GitHub Desktop.
Y Combinator - C# - [http://felipegte.com/2013/07/29/y-combinator-para-c-recursao-pero-no-mucho/]
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
using System; | |
using System.Collections.Generic; | |
using System.Diagnostics; | |
namespace YCombinatorCSharp | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
var stp = new Stopwatch(); | |
stp.Start(); | |
////Simple recursion | |
//Console.WriteLine(Use.FibonacciSimples(40)); | |
////Y w/ cache | |
//Console.WriteLine(Use.YCache(Use.FibonaccY)(40)); | |
////Y w/t cache | |
//Console.WriteLine(Use.Y(Use.FibonaccY)(40)); | |
stp.Stop(); | |
Console.WriteLine(stp.ElapsedMilliseconds); | |
Console.ReadLine(); | |
} | |
} | |
public class Use | |
{ | |
public static Func<decimal, decimal> YCache(Func<Func<decimal, decimal>, Func<decimal, decimal>> f, Dictionary<decimal, decimal> cache = null) | |
{ | |
if (cache == null) { cache = new Dictionary<decimal, decimal>(); } | |
return i => | |
{ | |
decimal result; | |
if (!cache.TryGetValue(i, out result)) | |
{ | |
var r = f(n => YCache(f, cache)(n))(i); | |
cache.Add(i, result = r); | |
} | |
return result; | |
}; | |
} | |
public static Func<decimal, decimal> Y(Func<Func<decimal, decimal>, Func<decimal, decimal>> f) | |
{ | |
Func<Func<dynamic, Func<decimal, decimal>>, Func<decimal, decimal>> _ = x => f(x1 => x(x)(x1)); | |
return _(x => f(y => x(x)(y))); | |
} | |
public static Func<decimal, decimal> FibonaccY(Func<decimal, decimal> f) | |
{ | |
return n => | |
{ | |
return n < 2 ? n : (f(n - 1) + f(n - 2)); | |
}; | |
} | |
public static long FibonacciSimples(long n) | |
{ | |
return n < 2 ? n : (FibonacciSimples(n - 1) + FibonacciSimples(n - 2)); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment