Skip to content

Instantly share code, notes, and snippets.

@logicmason

logicmason/yc.js

Last active June 18, 2021 01:46
Show Gist options
  • Save logicmason/0722b5b159a45f7a81b6 to your computer and use it in GitHub Desktop.
Save logicmason/0722b5b159a45f7a81b6 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. logicmason renamed this gist Dec 6, 2014. 1 changed file with 0 additions and 0 deletions.
    0 yc-fib.js → yc.js
    View file
    File renamed without changes.
  2. logicmason revised this gist Dec 6, 2014. 2 changed files with 43 additions and 2 deletions.
    17 changes: 15 additions & 2 deletions yc-fib.js
    View file
    Original file line number Diff line number Diff line change
    @@ -12,6 +12,19 @@ var factgen = function(fact) {
    };
    };

    console.log( Y(factgen)(5) ); // returns 120, i.e. 1 * 2 * 3 * 4 * 5
    var fibgen = function(fib) {
    // this naive solution has exponential runtime complexity
    return function(n) {
    return (n <= 2) ? 1 : fib(n-1) + fib(n-2);
    };
    };

    console.log( Y(factgen)(5) ); // returns 120, i.e., 1 * 2 * 3 * 4 * 5
    console.log( Y(fibgen)(7) ); // returns 13, i.e., the 7th fibonacci number

    var factorial = Y(factgen); // built entirely with anonymous functions
    var fibonacci = Y(fibgen);

    var factorial = Y(factgen); // built entirely with anonymous functions
    console.log( factorial(6) ); // 120
    console.log([1,2,3,4,5,6,7,8,9,10].map( fibonacci) ); // the first 10 fibonacci numbers
    console.log( fibonacci(35) ); // uh oh, already getting kind of slow due to poor algorithm
    28 changes: 28 additions & 0 deletions ymem.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,28 @@
    var fibgen = function(fib) {
    // this naive solution has exponential runtime complexity
    return function(n) {
    return (n <= 2) ? 1 : fib(n-1) + fib(n-2);
    };
    };

    var Ymem = function(proc) {
    // this Y combinator-like function caches the results of earlier calculations
    var results = {};
    return (function(x) {
    return proc(function(y) {
    if (results[y] === undefined) { results[y] = (x(x))(y); }
    return results[y];
    });
    })(function(x) {
    return proc(function(y) {
    if (results[y] === undefined) { results[y] = (x(x))(y); }
    return results[y];
    });
    });
    }

    // Using Ymem to cache results, fibgen no longer has exponential runtime complexity
    var fibonacci = Ymem(fibgen);
    console.log([1,2,3,4,5,6,7,8,9,10].map( fibonacci) ); // the first 10 fibonacci numbers
    console.log( fibonacci(35) ); // quickly calculates solution of 9227465
    console.log( fibonacci(120) ); // still calculates solution almost instantly
  3. logicmason revised this gist Dec 6, 2014. 1 changed file with 7 additions and 8 deletions.
    15 changes: 7 additions & 8 deletions yc-fib.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,18 +1,17 @@
    var Y = function (proc) {
    return (function (x) {
    return proc(function (y) { return (x(x))(y);});
    })(function (x) {
    return proc(function (y) { return (x(x))(y);});
    var Y = function(proc) {
    return (function(x) {
    return proc(function(y) { return (x(x))(y);});
    })(function(x) {
    return proc(function(y) { return (x(x))(y);});
    });
    };

    var factgen = function (fact) {
    var factgen = function(fact) {
    return function(n) {
    return (n === 0) ? 1 : n * fact(n-1); // calls argument, not self
    };
    };

    console.log( Y(factgen)(4) );
    console.log( Y(factgen)(6) );
    console.log( Y(factgen)(5) ); // returns 120, i.e. 1 * 2 * 3 * 4 * 5

    var factorial = Y(factgen); // built entirely with anonymous functions
  4. logicmason created this gist Dec 4, 2014.
    18 changes: 18 additions & 0 deletions yc-fib.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,18 @@
    var Y = function (proc) {
    return (function (x) {
    return proc(function (y) { return (x(x))(y);});
    })(function (x) {
    return proc(function (y) { return (x(x))(y);});
    });
    };

    var factgen = function (fact) {
    return function(n) {
    return (n === 0) ? 1 : n * fact(n-1); // calls argument, not self
    };
    };

    console.log( Y(factgen)(4) );
    console.log( Y(factgen)(6) );

    var factorial = Y(factgen); // built entirely with anonymous functions