Javascript 中使用 ES6 Y 组合器的有限递归次数

Question

我在 Javascript 中遇到了另一个关于递归的 SO 问题的答案，它在 ES6 中使用 Y 组合器给出了一个非常简洁的形式，使用 ES6 的粗箭头，我想 嘿, 使用起来会很好 - 然后 15 分钟左右后又转回 hm，也许不是 .

我以前参加过一些 Haskell/Idris 会谈和运行一些代码，并且熟悉标准 JS，所以希望我能够解决这个问题，但是不能'不太明白一个简单的 "do n recursions and return" 应该怎么走，以及在哪里实现递减计数器。

我只是想简化获取 DOM 元素的第 n^th 个父节点，并且似乎有更密集的解释所有指南比像这样的简单应用程序的例子。

我第一个看到的example是：

const Y = a => (a => a(a))(b => a(a => b(b)(a)));

而 this 最近的答案给出：

const U = f => f (f)
const Y = U (h => f => f (x => h(h)(f)(x)))

...其中给出了内部函数可能是什么的示例，以及一些示例输出，但是引入 U 组合器并不能真正帮助我澄清这一点。

在第一个示例中，我无法真正开始理解 b 在我的情况下可能是什么 - 我知道我需要一个函数 a 到 return 父节点：

const par = function(node) {
  return node.parentNode;
}

我想到了以下内容：

function RecParentNode(base_node, n) {
  // ES6 Y-combinator, via: 
  // define immutable [const] functions `Y` and `fn` [`fn` uses `Y`]
  // the arguments of `Y` are another two functions, `a` and `b`
  const Y = par=>(par=>par(par))(b=>par(par=>b(b)(par)));
  const fn = Y(fn => n => {
    console.log(n);
    if (n > 0) {
      fn(n - 1);
    }
  });
}

但后来不知道如何处理周围的备用 b，正要将其全部删除，只是忘了我打扰了。

我只想应用 par 函数 n 次，因为我知道的唯一选择是链接 .parentNode.parentNode.parentNode... 或作弊和转向一个字符串进入 eval 调用。

希望熟悉函数式 JS 的人可以帮助我了解如何使用 Y 组合器来制作此辅助函数 RecParentNode - 谢谢！

Answer 1

如果可以选择命令式编程：

 function getParent(el, n){
   while(n--) el = el.parentNode;
   return el;
}

使用函数递归你可以做到：

 const Y = f => x => f (Y (f)) (x); // thanks to @Naomik
 const getParent = Y(f => el => n => n ? f(el.parentNode)(n - 1) : el);

 console.log(getParent(document.getElementById("test"))(5));

让我们从头开始构建这个 Y-Combinator。由于它通过自身的 Y-Combinator 调用函数，因此 Y-Combinator 需要对自身的引用。为此，我们首先需要一个 U-Combinator：

 (U => U(U))

现在我们可以用我们的 Y 组合器调用 U 组合器，以便它获得自引用：

 (U => U(U))
 (Y => f => f( Y(Y)(f) ))

然而，这有一个问题：函数被调用时使用 Y-Combinator 引用，而 Y-Combinator 引用被调用时被调用....我们得到了无限递归。 Naomik outlined that here。解决方案是添加另一个在使用函数时调用的柯里化参数（例如 x），然后创建另一个递归组合器。所以我们只得到我们实际需要的递归量：

 (U => U(U))
 (Y => f => x => f( Y(Y)(f) )(x) )
 (f => n => n ? f(n - 1): n)(10) // a small example

我们也可以这样重构它：

 (f => (U => U(U))(Y => f(x => Y(Y)(x))))
 (f => n => n ? f(n - 1): n)(10) // a small example

为了得到你的第一个片段，所以基本上是同一件事，只是通过阴影重新排序和混淆了一点。

所以现在只有在 f(n-1) 被调用时才会创建另一个组合器，这只会在 n? 时发生，所以我们现在有一个退出条件。现在我们终于可以将我们的节点添加到整个事物中了：

 (U => U(U))
 (Y => f => x => f( Y(Y)(f) )(x) )
 (f => el => n => n ? f(el.parentNode)(n - 1): el)
 (document.getElementById("test"))(10)

那将是 纯功能性的 ，但这并不是真正有用，因为它使用起来非常复杂。如果我们存储函数引用，我们不需要 U 组合器，因为我们可以简单地获取 Y 引用。然后我们到达上面的片段。

Answer 2

尽职调查

嘿，你找到的那个答案是我的！但在查看 Y 组合子的各种定义之前，我们首先回顾一下它的目的：（强调我的）

In functional programming, the Y combinator can be used to formally define recursive functions in a programming language that doesn't support recursion (wikipedia)

现在，让我们回顾一下您的问题

I just wanted to simplify getting the nth parent node of a DOM element, and there seem to be more dense explain-all guides than examples of simple applications like this.

JavaScript 支持直接递归，这意味着函数可以直接通过名称调用自身。无需使用 U 或 Y 组合器。现在要设计一个递归函数，我们需要确定我们的 base 和 inductive case(s)

基本情况 – n 为零； return node
归纳案例 1 – n 不是零，但 node 为空；我们无法获得空节点的父节点； return undefined（如果你愿意，也可以是一些错误）
归纳案例 2 - n 不为零且 node 不为空；重复使用节点的父节点并将 n 减 1.

下面我们把nthParent写成一个纯函数表达式。为了简化后面的讨论，我们将在curried form中定义它的函数。

const Empty =
  Symbol ()

const nthParent = (node = Empty) => (n = 0) =>
  n === 0
    ? node
    : node === Empty
      ? undefined // or some kind of error; this node does not have a parent
      : nthParent (node.parentNode) (n - 1)
  
const Node = (value = null, parentNode = Empty) =>
  ({ Node, value, parentNode })

const data =
  Node (5, Node (4, Node (3, Node (2, Node (1)))))

console.log
  ( nthParent (data) (1) .value             // 4
  , nthParent (data) (2) .value             // 3
  , nthParent (data) (3) .value             // 2
  , nthParent (data) (6)                    // undefined
  )

但是如果...

所以假设您运行您的程序带有 JavaScript 不支持直接递归的解释器... 现在您有一个用例组合器

为了删除按名称调用递归，我们将整个函数包装在另一个 lambda 中，其参数 f（或您选择的名称）将是递归机制本身。它是 nthParent 的直接替代品 – 粗体

的变化

const nthParent = <b>Y (f =></b> (node = Empty) => (n = 0) =>
  n === 0
    ? node
    : node === Empty
      ? undefined
      : <del>nthParent</del> <b>f</b> (node.parentNode) (n - 1)<b>)</b>

现在我们可以定义Y

const Y = f =>
  f (Y (f))

并且我们可以使用与之前类似的技术来移除 Y 和 U 中的直接递归——更改 bold

const U = f =>
  f (f)

const Y = <b>U (g => </b>f =>
  f (<del>Y</del> <b>U (g)</b> (f))<b>)</b>

但是为了让它在 JavaScript 中工作，它使用 applicative order evaluation, we must delay evaluation using eta expansion – 更改 bold

const U = f =>
  f (f)

const Y = U (g => f =>
  f (<b>x => </b> U (g) (f) <b>(x)</b>))

大家在一起

const U = f =>
  f (f)
  
const Y = U (g => f =>
  f (x => U (g) (f) (x)))

const Empty =
  Symbol ()

const nthParent = Y (f => (node = Empty) => (n = 0) =>
  n === 0
    ? node
    : node === Empty
      ? undefined // or some kind of error; this node does not have a parent
      : f (node.parentNode) (n - 1))
  
const Node = (value = null, parentNode = Empty) =>
  ({ Node, value, parentNode })

const data =
  Node (5, Node (4, Node (3, Node (2, Node (1)))))

console.log
  ( nthParent (data) (1) .value             // 4
  , nthParent (data) (2) .value             // 3
  , nthParent (data) (3) .value             // 2
  , nthParent (data) (6)                    // undefined
  )

现在我希望您明白为什么 Y 组合器存在以及为什么您不会在 JavaScript 中使用它。在另一个答案中，我试图通过使用来帮助读者更深入地了解 Y 组合子。如果您感兴趣，我邀请您阅读。

实用

当 JavaScript 已经支持直接递归时，使用 Y 组合子没有意义。下面，以非柯里化形式

查看 nthParent 的更实用的定义

const nthParent = (node = Empty, n = 0) =>
  n === 0
    ? node
    : node === Empty
      ? undefined // or some kind of error; this node does not have a parent
      : nthParent (node.parentNode, n - 1)

但是那些最大递归深度堆栈溢出错误呢？如果我们有一个节点有数千层深的深树，上面的函数就会产生这样的错误。在 I introduce several ways to work around the problem. It is possible to write stack-safe recursive functions in a language that doesn't support direct recursion and/or tail call elimination!

Javascript 中使用 ES6 Y 组合器的有限递归次数

Finite number of recursions in Javascript with ES6 Y-combinator

javascript

recursion

y-combinator