haskell - “tying the knot”的解释

Question

在阅读 Haskell 相关的东西时，我有时会遇到“打结”这个表达，我想我理解它的作用，但不理解它的作用。

那么，对于这个概念有什么好的、基本的、简单易懂的解释吗？

Answer 1

打结是循环数据结构问题的解决方案。在命令式语言中，您可以通过首先创建一个非循环结构来构建循环结构，然后返回并修复指针以添加循环性。

假设您想要一个包含元素“0”和“1”的二元素循环列表。这似乎是不可能构造的，因为如果您创建“1”节点，然后创建“0”节点来指向它，那么您就无法返回并修复“1”节点以指向“0”节点。因此，您遇到了先有鸡还是先有蛋的情况，两个节点都需要先存在才能创建。

以下是在 Haskell 中的操作方法。考虑以下值:

alternates = x where
   x = 0 : y
   y = 1 : x

在非惰性语言中，由于未终止的递归，这将是一个无限循环。但在 Haskell 中，惰性求值做了正确的事情:它生成一个二元素循环列表。

要了解它在实践中如何工作，请考虑运行时会发生什么。惰性求值的通常“thunk”实现将未求值的表达式表示为包含函数指针以及要传递给函数的参数的数据结构。计算此值时，thunk 会被实际值替换，以便将来的引用不必再次调用该函数。

当您获取列表的第一个元素时，“x”将被计算为值(0，&y)，其中“&y”位是指向“y”值的指针。由于 'y' 尚未被评估，这目前是一个 thunk。当您获取列表的第二个元素时，计算机会跟踪从 x 到该 thunk 的链接并对其进行评估。它的计算结果为 (1, &x)，或者换句话说，是一个返回原始“x”值的指针。现在内存中有一个循环列表。程序员不需要修复后向指针，因为惰性求值机制会为您完成此操作。