Last active
March 27, 2018 20:01
-
-
Save corlaez/00d5139b75525d3c7b208b5dbb75c43d to your computer and use it in GitHub Desktop.
My Y combinator implementation, am I missing something?
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
// 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 | |
*/ |
: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
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!