+
1
|
list
|
skin
|
login
|
editor
α-wwwiki
::
jsYcombinator
user:none
(2080 bytes)
{h4 Y-combinator in javascript} _p Sources : {a {@ href="http://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/"}y-combinator-in-javascript}, [[y-combinator-for-dysfunctional-non-schemers|http://rayfd.me/2007/05/06/y-combinator-for-dysfunctional-non-schemers/]] {p A "functional" is just a function that takes another function as input. The Y combinator finds the fixed point of the "functional" passed in as an argument. Thus, the Y combinator satisfies the property : {b Y(F) = F(Y(F))}. Note that Y does not reference itself.} {pre °° var Y = function (F) { return (function (x) { return F(function (y) { return (x(x))(y); }); }) (function (x) { return F(function (y) { return (x(x))(y); }); }); }; °°} {p In fact, all functions above are anonymous ! FactGen is the functional whose fixed point is factorial. That is, if you pass the factorial function to FactGen, you get back the factorial function. Since the Y combinator returns the fixed point of a functional, applying the Y combinator to FactGen returns the factorial function ! Note that FactGen does not reference itself.} {pre °° var FactGen = function (fact) { return (function(n) { return ((n == 0) ? 1 : (n*fact(n-1))) ; }); } ; getId('result').innerHTML = (Y(FactGen))(6) ; °°} {p {input {@ type="submit" value="Evaluate" onclick ="°° var Y = function (F) { return (function (x) { return F(function (y) { return (x(x))(y); }); }) (function (x) { return F(function (y) { return (x(x))(y); }); }); }; var FactGen = function (fact) { return (function(n) { return ((n == 0) ? 1 : (n*fact(n-1))) ; }); } ; getId('result').innerHTML = (Y(FactGen))(6) ; °°"}}} {pre {@ id="result"} ... } _h6 Y-combinator in LISP {pre (define Y (lambda (le) ((lambda (f) (f f)) (lambda (f) (le (lambda (x) ((f f) x))))))) }