Skip to content

Instantly share code, notes, and snippets.

@corlaez
Last active March 27, 2018 20:01
Show Gist options
  • Save corlaez/00d5139b75525d3c7b208b5dbb75c43d to your computer and use it in GitHub Desktop.
Save corlaez/00d5139b75525d3c7b208b5dbb75c43d to your computer and use it in GitHub Desktop.
My Y combinator implementation, am I missing something?
// My point is that we could have a simpler Y combinator
// I think the lambda would be λf.λx. f f x
// not sure about that. I have only read about this today, so let me know
// what I am missing.
// My Y combinator (am i violating some lambda rule?)
const Y2 = f => x => f(f)(x)
// This proposal implementation requires spetial input functions
// note additional `(fact)` in `fact(fact)(n-1)`
// however I don't think I am violating some self referenciality rule
// as fact is taken as a parameter
// But I might be wrong, let me know
var factgen2 = fact =>
n => (n === 0) ? 1 : n * fact(fact)(n-1);
var fibgen2 = fib =>
n => (n <= 2) ? 1 : fib(fib)(n-1) + fib(fib)(n-2);
var factorial2 = Y2(factgen2); // built entirely with anonymous functions
var fibonacci2 = Y2(fibgen2);
console.log( factorial2(6) ); // 720
console.log([1,2,3,4,5,6,7,8,9,10].map( fibonacci2) ); // the first 10 fibonacci numbers
console.log( fibonacci2(15) ); // uh oh, already getting kind of slow due to poor algorithm
// Motivation:
// I read some articles, implemented my own Y combinator and then stumble on this:
// https://gist.github.com/logicmason/0722b5b159a45f7a81b6
// I reduced logicmason's Y combinator in a more compact form
var Lxfxx = f => x => f( y => x(x)(y) );
var Y = f => Lxfxx(f)( Lxfxx(f) ); // which follows Y's definition closely apparently
// However I found mine simpler and decided to write this gist.
/* Logicmason's tests for comparison
var factgen = fact =>
n => (n === 0) ? 1 : n * fact(n-1);
var fibgen = fib =>
n => (n <= 2) ? 1 : fib(n-1) + fib(n-2);
var factorial = Y(factgen); // built entirely with anonymous functions
var fibonacci = Y(fibgen);
console.log( factorial(6) ); // 720
console.log([1,2,3,4,5,6,7,8,9,10].map( fibonacci) ); // the first 10 fibonacci numbers
console.log( fibonacci(15) ); // uh oh, already getting kind of slow due to poor algorithm
*/
@DrBoolean
Copy link

Looks like:
const Y2 = f => x => f(f)(x) = const Y2 = f => f(f)

Just factor out the x.

That turns out to be the U combinator.

Neat!

@corlaez
Copy link
Author

corlaez commented Mar 27, 2018

:O I will try to look ab out it! Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment