javascript:递归匿名函数？

Question

假设我有一个基本的递归函数:

function recur(data) {
    data = data+1;
    var nothing = function() {
        recur(data);
    }
    nothing();
}

如果我有匿名功能,我怎么能这样做...

(function(data){
    data = data+1;
    var nothing = function() {
        //Something here that calls the function?
    }
    nothing();
})();

我想要一种方法来调用调用这个函数的函数...我已经看到某个地方的脚本(我记不清哪里)可以告诉你一个被调用的函数的名字,但我记不起任何一个那个信息现在.

Answer 1

你可以给功能的名字,甚至当你正在创建的函数作为值,而不是一个"函数声明"的声明.换一种说法:

(function foo() { foo(); })();

是一个堆栈递归函数.现在,也就是说,你可能根本不想这样做,因为Javascript的各种实现存在一些奇怪的问题.(注意 - 这是一个相当古老的评论; Kangax博客文章中描述的一些/很多/所有问题可能会在更现代的浏览器中修复.)

当你给出这样的名字时,这个名字在功能之外是不可见的(好吧,它不应该是;这是奇怪之一).这就像Lisp中的"letrec".

至于arguments.callee那种情况在"严格"模式下是不允许的,并且通常被认为是一件坏事,因为它会使一些优化变得困难.它也比人们预期的要慢得多.

编辑 - 如果你想拥有一个可以调用自身的"匿名"函数的效果,你可以做这样的事情(假设你将函数作为回调传递或类似的东西):

asyncThingWithCallback(params, (function() {
  function recursive() {
    if (timeToStop())
      return whatever();
    recursive(moreWork);
  }
  return recursive;
})());

这样做是使用一个漂亮,安全,未破坏的IE函数声明语句定义一个函数,创建一个名称不会污染全局名称空间的本地函数.包装器(真正的匿名)函数只返回本地函数.

Answer 2

人们在评论中谈到了Y组合,但没有人把它作为答案.

Y组合器可以在javascript中定义如下:(感谢steamer25的链接)

var Y = function (gen) {
  return (function(f) {
    return f(f);
  }(function(f) {
    return gen(function() {
      return f(f).apply(null, arguments);
    });
  }));
}

当你想传递你的匿名函数时:

(Y(function(recur) {
  return function(data) {
    data = data+1;
    var nothing = function() {
      recur(data);
    }
    nothing();
  }
})());

关于这个解决方案最重要的一点是你不应该使用它.

Answer 3

U组合子

U组合器接受一个函数并将其应用于自身.所以你给它的功能应该至少有一个参数将绑定到函数(本身)

在下面的示例中,我们没有退出条件,因此我们将无限循环,直到发生堆栈溢出

const U = f => f (f)

U (f => (console.log ('stack overflow imminent!'), U (f)))

我们可以使用各种技术来阻止无限递归.在这里,我将编写我们的匿名函数来返回另一个等待输入的匿名函数; 在这种情况下,一些数字.当提供一个数字时,如果它大于0,我们将继续重复,否则返回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 0

这里没有立即明白的是我们的函数,当首次使用U组合器应用于自身时,它返回一个等待第一个输入的函数.如果我们为此命名,可以使用lambdas(匿名函数)有效地构造递归函数

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 0

只有这不是直接递归 - 一个使用自己的名称调用自身的函数.我们的定义countDown不会在其身体内部引用自身,并且仍然可以递归

// 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)

如何使用U组合器从现有函数中删除自引用

在这里,我将向您展示如何使用递归函数,该函数使用对自身的引用并将其更改为使用U组合子代替自引用的函数

const factorial = x =>
  x === 0 ? 1 : x * factorial (x - 1)
  
console.log (factorial (5)) // 120

现在使用U组合器替换内部引用 factorial

const U = f => f (f)

const factorial = U (f => x =>
  x === 0 ? 1 : x * U (f) (x - 1))

console.log (factorial (5)) // 120

基本的替代模式是这样的.请记住,我们将在下一节中使用类似的策略

// self reference recursion
const foo =         x => ...   foo (nextX) ...

// remove self reference with U combinator
const foo = U (f => x => ... U (f) (nextX) ...)

Y组合子

相关:U和Y组合使用镜像类比解释

在上一节中,我们看到了如何将自引用递归转换为不依赖于使用U组合器的命名函数的递归函数.因为必须记住总是将函数作为第一个参数传递给自己,所以有点烦恼.好吧,Y-combinator建立在U-co​​mbinator之上,并消除了那个乏味的位.这是一件好事,因为消除/降低复杂性是我们制作功能的主要原因

首先,让我们推导出我们自己的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)))

现在我们将看到它的用法与U-combinator的比较.请注意,重复一次,而不是U (f)我们可以简单地打电话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 ()))

现在我将演示countDown使用的程序Y- 你会看到程序几乎相同,但Y组合器使事情更清洁

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 0

现在,我们可以看到factorial,以及

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)) // 120

具有多于1个参数的U和Y组合子

在上面的例子中,我们看到了如何循环和传递参数以跟踪计算的"状态".但是,如果我们需要跟踪其他状态呢？

我们可以使用像数组之类的复合数据......

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)) // 55

但这很糟糕,因为它暴露了内部状态(计数器f和recur).如果我们可以打电话a来获得我们想要的答案,那就太好了.

使用我们对curried函数(一元(1-paramter)函数的序列)的了解,我们可以轻松实现我们的目标,而无需修改我们的定义b或依赖复合数据或高级语言功能.

fibonacci (7)仔细看下面的定义.我们会立即将Y和fibonacci这必将对0和1分别.现在斐波那契只是在等待提供的最后一个参数a.当我们递归时,我们必须调用b(而不是x)因为我们的函数是以curry形式.

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 13

这种模式可用于定义各种函数.下面我们将看到使用定义的两个函数f (a) (b) (x)组合子(f (a,b,x)和Y)和衍生物range,reduce.

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 13

这是所有无名的OMG

因为我们在这里使用纯函数,所以我们可以用任何命名函数替换它的定义.观察当我们采用斐波那契并用其表达式替换命名函数时会发生什么

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 ]

而且你有它 - reduce使用匿名函数递归计算

Answer 4

使用"匿名对象"可能最简单:

({
  do: function() {
    console.log("don't run this ...");
    this.do();
  }
}).do();

您的全球空间完全没有受到污染.这很简单.您可以轻松利用对象的非全局状态.

Answer 5

我不会这样做作为内联函数.它正在推动良好品味的界限,并没有真正得到任何东西.

如果你真的必须,那arguments.callee就像法布里奇奥的回答一样.然而,这通常被认为是不可取的,并且在ECMAScript第五版的"严格模式"中是不允许的.虽然ECMA 3和非严格模式不会消失,但在严格模式下工作可以提供更多可能的语言优化.

也可以使用命名内联函数:

(function foo(data){
    data++;
    var nothing = function() {
        foo(data);
    }
    nothing();
})();

然而,最好避免使用命名的内联函数表达式,因为IE的JScript会给它们带来一些不好的东西.在上面的示例中,foo错误地污染了IE中的父作用域,并且父作用foo是与foo内部看到的单独的实例foo.

将它放在内联匿名函数中的目的是什么？如果您只是想避免污染父作用域,您当然可以将您的第一个示例隐藏在另一个自调用匿名函数(命名空间)中.你是否真的需要nothing在递归周围创建每次的新副本？使用包含两个简单的相互递归函数的命名空间可能会更好.

Answer 6

(function(data){
    var recursive = arguments.callee;
    data = data+1;
    var nothing = function() {
        recursive(data)
    }
    nothing();
})();

Answer 7

你可以这样做:

(foo = function() { foo(); })()

或者在你的情况下:

(recur = function(data){
    data = data+1;
    var nothing = function() {
        if (data > 100) return; // put recursion limit
        recur(data);
    }
    nothing();
})(/* put data init value here */ 0);