11 ms·
Recursions without names: Introduction to the Y combinator in JavaScript
- ChicagoBoy11 10y agoA question about the klipse plugin: Does code inside it have access to DOM elements just as javascript running on the console would? Would be a fantastic addition that could really make developing an interactive coding exercise for kids learning about the web a breeze!
- viebel 10y agoIndeed, the klipse plugin has access to DOM elements. What ideas do you have for kids? I have tried to do something for kids here: kids.klipse.tech The klipse plugin concept is explained in details: 1. http://blog.klipse.tech/javascript/2016/06/20/blog-javascript.html http://blog.klipse.tech/javascript/2016/06/20/blog-javascrip... 2. https://github.com/viebel/klipse https://github.com/viebel/klipse
- nightcracker 10y agoIf I'm not mistaken, this isn't the full Y combinator yet. It's a partial step towards deriving the full Y combinator. (f => (x => x(x))(y => f(x => y(y)(x)))) (func => n => (n === 0) ? 1 : (n * func(n - 1))) (19) Notice that the ugly func(func)(n-1) recursive call with the proper Y combinator simply became func(n-1). The full Y combinator is also vastly more mystical and less obvious than the partial step :)
- thethirdone 10y ago> The full Y combinator is also vastly more mystical and less obvious than the partial step :) The full Y conbinator simply binds func to func(func) as seen in `(y => f(x => y(y)(x))))`, an easy jump to make and pretty easy to understand.
- viebel 10y agoThe full Y combinator is presented in the sequel of the current article: http://blog.klipse.tech/lambda/2016/08/10/pure-y-combinator-javascript.html http://blog.klipse.tech/lambda/2016/08/10/pure-y-combinator-...
- furhxbbd 10y agoFor what purpose?
- qwertyuiop924 10y agoQuoth xkcd, "Tail recusion is its own reward." In all seriousness, even if the y combinator is practically useless in languages that don't have proper TCO (which is specced for ES7), it's a useful learning tool, is powerfully mind expanding, and can help to demonstrate the power of the λ-calculus.
- viebel 10y agoThere is a practical application for recursive memoization: http://blog.klipse.tech/lambda/2016/08/10/y-combinator-app-javascript.html http://blog.klipse.tech/lambda/2016/08/10/y-combinator-app-j...
- kristianp 10y agohttp://xkcd.com/1270/ http://xkcd.com/1270/
- gohrt 10y agoIs the Y-combinator any more or less dependent on TCO than regular recursion? The Y combinator is useless in languages that already have builtin support for recursive functions.
- viebel 10y agoNot useless, almost useless: You can do elegant recursive memoization with the Y combinator as explained here http://blog.klipse.tech/lambda/2016/08/10/y-combinator-app-javascript.html http://blog.klipse.tech/lambda/2016/08/10/y-combinator-app-j...
- qwertyuiop924 10y agoNo, Y is handy for defining nameless recursive functions, but it blows the stack even faster if you don't have TCO.
- louthy 10y agoObligatory 'To Dissect a Mockingbird' link: http://dkeenan.com/Lambda/index.htm http://dkeenan.com/Lambda/index.htm If you have never read this before, then I highly recommend it. It's a beautiful way to picture combinators.
- qwertyuiop924 10y agoIndeed. It's by far best explanation of the concept that I've seen, and it, along with some of Matt Might's posts, helped me gain a deeper appreciation for concepts like Church Encoding, and λ-calculus in general.
- usagimaru 10y agoJim Weirich had a good couple talks about building a Y combinator in a couple languages. Here's his JavaScirpt version: https://vimeo.com/45140590 https://vimeo.com/45140590 RIP
- millstone 10y agoThe code samples fail in Safari. The first one prints "SyntaxError: Unexpected token '>'".
- dsego 10y agoYou need Safari Technology Preview for ES6 support.
- Sacho 10y agoYour version of Safari most likely lacks support for ES6 features like arrow functions[0], you could use babel[1] to transpile the code to ES5: (function (f) { return f(f); })(function (func) { return function (n) { return n === 0 ? 1 : n * func(func)(n - 1); }; })(19); [0] http://caniuse.com/#feat=arrow-functions http://caniuse.com/#feat=arrow-functions [1] https://babeljs.io/repl/ https://babeljs.io/repl/
- prashnts 10y agoI find the Python implementation is slightly more elegant: (lambda f: f(f)) (lambda fn: lambda n: 1 if n == 0 else (n * fn(fn)(n - 1))) (5)
- viebel 10y agoYeah. But I didn't find a way to run python code in the browser. Currently in Klipse, we support javascript, ruby, clojure and php...
- hughbetcha 10y agoTo be fair, the article would be more aptly titled "Recursion without function names". In any recursion you need a way to reference the original function somehow. They're using a function parameter to accomplish that via indirection.
- viebel 10y agoThere are no names except function arguments. No 'x=...'
- hughbetcha 10y agoPlease reread my post. The function parameter is the name.
- viebel 10y agoDo you know a language without argument names?
- hughbetcha 10y agoYou're missing the point. Nevermind.
- jomamaxx 10y agoKitten -> meet laser pointer Nerd -> meet article