2

我遇到了另一个关于 Javascript 中递归的 SO 问题的答案，它使用 Y-combinator 在 ES6 中给出了一个非常简洁的形式，使用 ES6 的胖箭头，并认为嘿，使用起来会很整洁- 然后 15 分钟左右后来又绕回hm，也许不是。

我之前参加过一些 Haskell/Idris 讲座并运行过一些代码，并且熟悉标准 JS，所以希望我能够弄清楚这一点，但不太明白如何简单地“进行n递归并返回” " 应该去，以及在哪里实现一个递减计数器。

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

我第一次看到的例子是：

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

虽然这个更新的答案给出了：

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

...给出了内部功能可能是什么的示例，以及一些示例输出，但是引入 U-combinator 并不能真正帮助我澄清这一点。

在第一个示例中，我无法真正开始理解b我的情况 - 我知道我需要一个函数a来返回父节点：

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

我想出了以下内容：

function RecParentNode(base_node, n) {
  // ES6 Y-combinator, via: https://stackoverflow.com/a/32851197/2668831
  // 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-combinator 来制作这个辅助函数RecParentNode- 谢谢！

4

2 回答 2

4

尽职调查

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

在函数式编程中，Y 组合器可用于在不支持递归的编程语言中正式定义递归函数（维基百科）

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

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

JavaScript 支持直接递归，这意味着函数可以通过名称直接调用自己。不需要使用U或Y组合子。现在要设计一个递归函数，我们需要确定我们的基础和归纳案例

  • 基本情况——n为零；返回node
  • 归纳案例 1 –n不是零，而是空node的；我们无法获得空节点的父节点；返回undefined（或一些错误，如果你愿意）
  • 归纳案例 2 -n不为零node且不为空；使用节点的父节点递归并减n1。

下面我们写成nthParent纯函数表达式。为了简化后面的讨论，我们将它定义为柯里化形式的函数。

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 = Y (f => (node = Empty) => (n = 0) =>
  n === 0
    ? node
    : node === Empty
      ? undefined
      : nthParent f (node.parentNode) (n - 1))

现在我们可以定义Y

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

我们可以使用与以前类似的技术来删除Y和U中的直接递归——粗体的变化

const U = f =>
  f (f)

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

但是为了让它在使用应用顺序评估的 JavaScript 中工作，我们必须使用eta 扩展延迟评估- 更改为粗体

const U = f =>
  f (f)

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

现在都在一起了

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)

但是那些最大递归深度堆栈溢出错误呢？如果我们有一棵具有数千层深的节点的树，上面的函数就会产生这样的错误。在这个答案中，我介绍了几种解决问题的方法。可以用不支持直接递归和/或尾调用消除的语言编写堆栈安全递归函数！

于 2018-02-12T21:43:52.750 回答
0

如果命令式编程是一种选择：

 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 在这里概述了这一点。解决方案是添加另一个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 引用。然后我们到达上面的片段。

于 2018-02-09T22:39:16.527 回答