javascript: recursive anonymous function?
Let's say I have a basic recursive function:
function recur(data) {
data = data+1;
var nothing = function() {
recur(data);
}
nothing();
}
How could I do this if I have an anonymous function such as...
(function(data){
data = data+1;
var nothing = function() {
//Something here that calls the function?
}
nothing();
})();
I'd like a way to call the function that called this function... I've seen scripts somewhere (I can't remember where) that can tell you the name of a function called, but I can't recall any of that information right now.
Solution 1:
You can give the function a name, even when you're creating the function as a value and not a "function declaration" statement. In other words:
(function foo() { foo(); })();
is a stack-blowing recursive function. Now, that said, you probably don't may not want to do this in general because there are some weird problems with various implementations of Javascript. (note — that's a fairly old comment; some/many/all of the problems described in Kangax's blog post may be fixed in more modern browsers.)
When you give a name like that, the name is not visible outside the function (well, it's not supposed to be; that's one of the weirdnesses). It's like "letrec" in Lisp.
As for arguments.callee, that's disallowed in "strict" mode and generally is considered a bad thing, because it makes some optimizations hard. It's also much slower than one might expect.
edit — If you want to have the effect of an "anonymous" function that can call itself, you can do something like this (assuming you're passing the function as a callback or something like that):
asyncThingWithCallback(params, (function() {
function recursive() {
if (timeToStop())
return whatever();
recursive(moreWork);
}
return recursive;
})());
What that does is define a function with a nice, safe, not-broken-in-IE function declaration statement, creating a local function whose name will not pollute the global namespace. The wrapper (truly anonymous) function just returns that local function.
Solution 2:
People talked about the Y combinator in comments, but no one wrote it as an answer.
The Y combinator can be defined in javascript as follows: (thanks to steamer25 for the link)
var Y = function (gen) {
return (function(f) {
return f(f);
}(function(f) {
return gen(function() {
return f(f).apply(null, arguments);
});
}));
}
And when you want to pass your anonymous function:
(Y(function(recur) {
return function(data) {
data = data+1;
var nothing = function() {
recur(data);
}
nothing();
}
})());
The most important thing to note about this solution is that you shouldn't use it.
Solution 3:
U combinator
By passing a function to itself as an argument, a function can recur using its parameter instead of its name! So the function given to U should have at least one parameter that will bind to the function (itself).
In the example below, we have no exit condition, so we will just loop indefinitely until a stack overflow happens
const U = f => f (f) // call function f with itself as an argument
U (f => (console.log ('stack overflow imminent!'), U (f)))We can stop the infinite recursion using a variety of techniques. Here, I'll write our anonymous function to return another anonymous function that's waiting for an input; in this case, some number. When a number is supplied, if it is greater than 0, we will continue recurring, otherwise return 0.
const log = x => (console.log (x), x)
const U = f => f (f)
// when our function is applied to itself, we get the inner function back
U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)
// returns: (x => x > 0 ? U (f) (log (x - 1)) : 0)
// where f is a reference to our outer function
// watch when we apply an argument to this function, eg 5
U (f => x => x > 0 ? U (f) (log (x - 1)) : 0) (5)
// 4 3 2 1 0What's not immediately apparent here is that our function, when first applied to itself using the U combinator, it returns a function waiting for the first input. If we gave a name to this, can effectively construct recursive functions using lambdas (anonymous functions)
const log = x => (console.log (x), x)
const U = f => f (f)
const countDown = U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)
countDown (5)
// 4 3 2 1 0
countDown (3)
// 2 1 0Only this isn't direct recursion – a function that calls itself using its own name. Our definition of countDown does not reference itself inside of its body and still recursion is possible
// direct recursion references itself by name
const loop = (params) => {
if (condition)
return someValue
else
// loop references itself to recur...
return loop (adjustedParams)
}
// U combinator does not need a named reference
// no reference to `countDown` inside countDown's definition
const countDown = U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)How to remove self-reference from an existing function using U combinator
Here I'll show you how to take a recursive function that uses a reference to itself and change it to a function that employs the U combinator to in place of the self reference
const factorial = x =>
x === 0 ? 1 : x * factorial (x - 1)
console.log (factorial (5)) // 120Now using the U combinator to replace the inner reference to factorial
const U = f => f (f)
const factorial = U (f => x =>
x === 0 ? 1 : x * U (f) (x - 1))
console.log (factorial (5)) // 120The basic replacement pattern is this. Make a mental note, we will be using a similar strategy in the next section
// self reference recursion
const foo = x => ... foo (nextX) ...
// remove self reference with U combinator
const foo = U (f => x => ... U (f) (nextX) ...)
Y combinator
related: the U and Y combinators explained using a mirror analogy
In the previous section we saw how to transform self-reference recursion into a recursive function that does not rely upon a named function using the U combinator. There's a bit of an annoyance tho with having to remember to always pass the function to itself as the first argument. Well, the Y-combinator builds upon the U-combinator and removes that tedious bit. This is a good thing because removing/reducing complexity is the primary reason we make functions
First, let's derive our very own Y-combinator
// standard definition
const Y = f => f (Y (f))
// prevent immediate infinite recursion in applicative order language (JS)
const Y = f => f (x => Y (f) (x))
// remove reference to self using U combinator
const Y = U (h => f => f (x => U (h) (f) (x)))Now we will see how it's usage compares to the U-combinator. Notice, to recur, instead of U (f) we can simply call f ()
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
Y (f => (console.log ('stack overflow imminent!'), f ()))Now I'll demonstrate the countDown program using Y – you'll see the programs are almost identical but the Y combinator keeps things a bit cleaner
const log = x => (console.log (x), x)
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const countDown = Y (f => x => x > 0 ? f (log (x - 1)) : 0)
countDown (5)
// 4 3 2 1 0
countDown (3)
// 2 1 0And now we'll see factorial as well
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const factorial = Y (f => x =>
x === 0 ? 1 : x * f (x - 1))
console.log (factorial (5)) // 120As you can see, f becomes the mechanism for recursion itself. To recur, we call it like an ordinary function. We can call it multiple times with different arguments and the result will still be correct. And since it's an ordinary function parameter, we can name it whatever we like, such as recur below -
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const fibonacci = Y (recur => n =>
n < 2 ? n : recur (n - 1) + (n - 2))
console.log (fibonacci (10)) // 55U and Y combinator with more than 1 parameter
In the examples above, we saw how we can loop and pass an argument to keep track of the "state" of our computation. But what if we need to keep track of additional state?
We could use compound data like an Array or something...
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const fibonacci = Y (f => ([a, b, x]) =>
x === 0 ? a : f ([b, a + b, x - 1]))
// starting with 0 and 1, generate the 7th number in the sequence
console.log (fibonacci ([0, 1, 7]))
// 0 1 1 2 3 5 8 13But this is bad because it's exposing internal state (counters a and b). It would be nice if we could just call fibonacci (7) to get the answer we want.
Using what we know about curried functions (sequences of unary (1-paramter) functions), we can achieve our goal easily without having to modify our definition of Y or rely upon compound data or advanced language features.
Look at the definition of fibonacci closely below. We're immediately applying 0 and 1 which are bound to a and b respectively. Now fibonacci is simply waiting for the last argument to be supplied which will be bound to x. When we recurse, we must call f (a) (b) (x) (not f (a,b,x)) because our function is in curried form.
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const fibonacci = Y (f => a => b => x =>
x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)
console.log (fibonacci (7))
// 0 1 1 2 3 5 8 13This sort of pattern can be useful for defining all sorts of functions. Below we'll see two more functions defined using the Y combinator (range and reduce) and a derivative of reduce, map.
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const range = Y (f => acc => min => max =>
min > max ? acc : f ([...acc, min]) (min + 1) (max)) ([])
const reduce = Y (f => g => y => ([x,...xs]) =>
x === undefined ? y : f (g) (g (y) (x)) (xs))
const map = f =>
reduce (ys => x => [...ys, f (x)]) ([])
const add = x => y => x + y
const sq = x => x * x
console.log (range (-2) (2))
// [ -2, -1, 0, 1, 2 ]
console.log (reduce (add) (0) ([1,2,3,4]))
// 10
console.log (map (sq) ([1,2,3,4]))
// [ 1, 4, 9, 16 ]IT'S ALL ANONYMOUS OMG
Because we're working with pure functions here, we can substitute any named function for its definition. Watch what happens when we take fibonacci and replace named functions with their expressions
/* const U = f => f (f)
*
* const Y = U (h => f => f (x => U (h) (f) (x)))
*
* const fibonacci = Y (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)
*
*/
/*
* given fibonacci (7)
*
* replace fibonacci with its definition
* Y (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
*
* replace Y with its definition
* U (h => f => f (x => U (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
//
* replace U with its definition
* (f => f (f)) U (h => f => f (x => U (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
*/
let result =
(f => f (f)) (h => f => f (x => h (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
console.log (result) // 13And there you have it – fibonacci (7) calculated recursively using nothing but anonymous functions