haskell - “结缘”的解释

Question

在阅读与 Haskell 相关的内容时，我有时会遇到“打结”的表达，我想我理解它的作用，但不知道如何。

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

Answer 1

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

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

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

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

在非惰性语言中，由于未终止的递归，这将是一个无限循环。但是在 Haskell 中，惰性求值是正确的：它生成一个包含两个元素的循环列表。

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

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

Answer 2

这不是您所要求的，并且与 Haskell 没有直接关系，但 Bruce McAdam 的论文That About Wraps It Up以相当广的广度和深度探讨了这个主题。Bruce 的基本思想是使用称为 WRAP的显式打结运算符，而不是在 Haskell、OCaml 和其他一些语言中自动完成的隐式打结。这篇论文有很多有趣的例子，如果你对打结感兴趣，我想你会对这个过程有更好的感觉。