“tying the knot”的解释

Question

阅读 Haskell 相关内容时，我有时会遇到“tying the knot”这个表达式。我认为我理解它的作用，但不理解具体的实现方法。

那么，有没有任何好的、基础的、简单易懂的解释这个概念的资料呢？

- Magnus

---

请查看此处：http://www.haskell.org/haskellwiki/Tying_the_Knot。 - EBGreen

或者在这里。 :) - Alexey

Answer 1

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

假设您想要一个包含元素 "0" 和 "1" 的两个元素循环列表。这似乎是不可能的，因为如果您创建"1"节点，然后创建"0"节点并将其指向"1"节点，那么您无法返回并修复"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'值的指针。因此，你现在在内存中有一个循环列表。程序员不需要修复后置指针，因为惰性求值机制会为您完成此操作。

- Paul Johnson

---

这很容易！我想下一个问题是：如何在Haskell中将某些内容插入到双向链表中？ - Alexey

@Alexey - 基本的回答是：你可以复制整个列表，并将插入的元素添加进去。 Haskell 的数据结构是不可变的，这也是为什么我们很少使用双向链表的原因。 - Paul Johnson

我在互联网上找到了一些关于这个主题的讨论、演讲和文章，正在尝试从中学习，但是你的基本答案对我来说不太令人信服：如果在你的实现中复制双向链表的单个节点，则会复制整个列表，因此无法向其中添加任何内容。 - Alexey

Alexey，我的意思是你必须构建一个新列表，其中包含旧元素和新元素。 - Paul Johnson

我目前在思考如何使用“常数”额外空间，在“常数”时间内将项目插入到双向链表或图中。 - Alexey

@Alexey，你可能做不到这件事（除非有一些我没有考虑到的非常奇怪的边缘情况）。至少在纯代码中无法实现，但在ST或IO等类似的环境中做这样的事情并不难。 - semicolon

Answer 2

虽然不完全符合您的要求，也与Haskell没有直接关系，但Bruce McAdam的论文《That About Wraps It Up》在这个主题上有很广泛而深入的探讨。Bruce的基本想法是使用一个显式结绑操作符，称为WRAP，而不是Haskell、OCaml以及其他一些语言中自动完成的隐式结绑操作。该论文具有有趣的示例，如果您对结绑操作感兴趣，我认为您会更好地理解这个过程。

- Norman Ramsey