如何递归地在ES6中编写箭头函数？

Question

ES6中的箭头函数没有arguments属性,因此arguments.callee无法工作,即使只使用匿名函数也无法在严格模式下工作.

箭头函数无法命名,因此无法使用命名的函数表达式技巧.

那么......如何编写递归箭头函数？这是一个箭头函数,根据某些条件递归调用自身等等当然？

Answer 1

编写递归函数而不命名它是一个与计算机科学本身一样古老的问题(实际上,因为λ演算早于计算机科学),因为在λ演算中所有函数都是匿名的,但你仍然需要递归.

解决方案是使用固定点组合器,通常是Y组合器.这看起来像这样:

(y => 
  y(
    givenFact => 
      n => 
        n < 2 ? 1 : n * givenFact(n-1)
  )(5)
)(le => 
  (f => 
    f(f)
  )(f => 
    le(x => (f(f))(x))
  )
);

这将5递归计算阶乘.

注意:代码很大程度上基于此:Y Combinator用JavaScript解释.所有功劳都归功于原作者.我大多只是"协调"(你用ES/Harmony的新功能重构旧代码吗？)它.

Answer 2

Claus Reinke在esdiscuss.org网站上的讨论中回答了您的问题.

在ES6中,您必须定义他称之为递归组合子的东西.

 let rec = (f)=> (..args)=> f( (..args)=>rec(f)(..args), ..args )

如果要调用递归箭头函数,则必须使用箭头函数作为参数调用递归组合器,箭头函数的第一个参数是递归函数,其余参数是参数.递归函数的名称没有重要性,因为它不会在递归组合器之外使用.然后,您可以调用匿名箭头功能.在这里,我们计算6的阶乘.

 rec( (f,n) => (n>1 ? n*f(n-1) : n) )(6)

如果你想在Firefox中测试它,你需要使用递归组合器的ES5转换:

function rec(f){ 
    return function(){
        return f.apply(this,[
                               function(){
                                  return rec(f).apply(this,arguments);
                                }
                            ].concat(Array.prototype.slice.call(arguments))
                      );
    }
}

Answer 3

看起来您可以将箭头函数分配给变量并使用它来递归调用函数.

var complex = (a, b) => {
    if (a > b) {
        return a;
    } else {
        complex(a, b);
    }
};

Answer 4

使用您为其分配函数的变量,例如

const fac = (n) => n>0 ? n*fac(n-1) : 1;

如果你真的需要匿名,请使用Y组合器,如下所示:

const Y = (f) => ((x)=>f((v)=>x(x)(v)))((x)=>f((v)=>x(x)(v)))
… Y((fac)=>(n)=> n>0 ? n*fac(n-1) : 1) …

(丑,不是吗？)

Answer 5

特尔；博士：

const rec = f => f((...xs) => rec(f)(...xs));

这里有很多答案，对适当的 Y有变化——但这有点多余......问题是 Y 的通常解释方式是“如果没有递归会怎样”，所以 Y 本身不能指代自己。但是因为这里的目标是一个实用的组合器，所以没有理由这样做。有这个答案定义了rec使用本身，但它很复杂而且有点丑，因为它添加了一个参数而不是柯里化。

简单的递归定义的 Y 是

const rec = f => f(rec(f));

但由于 JS 并不懒惰，因此上面添加了必要的包装。

Answer 6

我发现提供的解决方案非常复杂，而且老实说无法理解其中的任何一个，所以我自己想出了一个更简单的解决方案（我确信它已经知道，但这是我的思考过程）：

所以你正在创建一个阶乘函数

x => x < 2 ? x : x * (???)

(???) 是函数应该调用自身的地方，但由于您无法命名它，所以明显的解决方案是将其作为参数传递给自身

f => x => x < 2 ? x : x * f(x-1)

但这行不通。因为当我们调用时f(x-1)，我们正在调用这个函数本身，并且我们刚刚将其参数定义为 1) f：函数本身，以及 2)x值。好吧，我们确实有这个函数本身，f还记得吗？所以先通过它：

f => x => x < 2 ? x : x * f(f)(x-1)
                            ^ the new bit

就是这样。我们刚刚创建了一个将自身作为第一个参数的函数，生成阶乘函数！只需将其直接传递给自身即可：

(f => x => x < 2 ? x : x * f(f)(x-1))(f => x => x < 2 ? x : x * f(f)(x-1))(5)
>120

您可以创建另一个将其参数传递给自身的函数，而不是编写两次：

y => y(y)

并将阶乘函数传递给它：

(y => y(y))(f => x => x < 2 ? x : x * f(f)(x-1))(5)
>120

繁荣。这是一个小公式：

(y => y(y))(f => x => endCondition(x) ? default(x) : operation(x)(f(f)(nextStep(x))))

对于将 0 到 之间的数字相加的基本函数x，endCondition当您需要停止重复时，因此x => x == 0。是您在满足default后给出​​的最后一个值，因此. 只是您在每次递归中执行的操作，例如阶乘中的乘法或斐波那契中的加法：。最后是要传递给函数的下一个值，通常是当前值减一：。申请：endConditionx => xoperationx1 => x2 => x1 + x2nextStepx => x - 1

(y => y(y))(f => x => x == 0 ? x : x + f(f)(x - 1))(5)
>15

Answer 7

用于任意数量参数的递归函数定义的通用组合器（不使用自身内部的变量）将是：

const rec = (le => ((f => f(f))(f => (le((...x) => f(f)(...x))))));

例如，这可以用来定义阶乘：

const factorial = rec( fact => (n => n < 2 ? 1 : n * fact(n - 1)) );
//factorial(5): 120

或字符串反转：

const reverse = rec(
  rev => (
    (w, start) => typeof(start) === "string" 
                ? (!w ? start : rev(w.substring(1), w[0] + start)) 
                : rev(w, '')
  )
);
//reverse("olleh"): "hello"

或中序树遍历：

const inorder = rec(go => ((node, visit) => !!(node && [go(node.left, visit), visit(node), go(node.right, visit)])));

//inorder({left:{value:3},value:4,right:{value:5}}, function(n) {console.log(n.value)})
// calls console.log(3)
// calls console.log(4)
// calls console.log(5)
// returns true