“喜结连理”的解释
在阅读 Haskell 相关的东西时，我有时会遇到“打结”这个表达，我想我理解它的作用，但不理解它的作用。
那么，对于这个概念有什么好的、基本的、简单易懂的解释吗？
In reading Haskell-related stuff I sometimes come across the expression “tying the knot”, I think I understand what it does, but not how.
So, are there any good, basic, and simple to understand explanations of this concept?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
打结是循环数据结构问题的解决方案。 在命令式语言中，您可以通过首先创建一个非循环结构来构造循环结构，然后返回并修复指针以添加循环性。
假设您想要一个包含元素“0”和“1”的二元素循环列表。 这似乎是不可能构造的，因为如果您创建“1”节点，然后创建“0”节点来指向它，那么您就无法返回并修复“1”节点以指向“0”节点。 因此，您遇到了先有鸡还是先有蛋的情况，两个节点都需要先存在才能创建。
以下是在 Haskell 中的操作方法。 考虑以下值：
在非惰性语言中，由于未终止的递归，这将是无限循环。 但在 Haskell 中，惰性求值做了正确的事情：它生成一个二元素循环列表。
要了解它在实践中如何工作，请考虑运行时发生的情况。 惰性求值的通常“thunk”实现将未求值的表达式表示为包含函数指针以及要传递给函数的参数的数据结构。 计算此值时，thunk 将被实际值替换，以便将来的引用不必再次调用该函数。
当您获取列表的第一个元素时，“x”将被计算为值（0，&y），其中“&y”位是指向“y”值的指针。 由于 'y' 尚未被评估，这目前是一个 thunk。 当您获取列表的第二个元素时，计算机会跟踪从 x 到此 thunk 的链接并对其进行评估。 它的计算结果为 (1, &x)，或者换句话说，是一个返回原始“x”值的指针。 现在你的内存中就有了一个循环列表。 程序员不需要修复后向指针，因为惰性求值机制会为您完成此操作。
Tying the knot is a solution to the problem of circular data structures. In imperative languages you construct a circular structure by first creating a non-circular structure, and then going back and fixing up the pointers to add the circularity.
Say you wanted a two-element circular list with the elements "0" and "1". It would seem impossible to construct because if you create the "1" node and then create the "0" node to point at it, you cannot then go back and fix up the "1" node to point back at the "0" node. So you have a chicken-and-egg situation where both nodes need to exist before either can be created.
Here is how you do it in Haskell. Consider the following value:
In a non-lazy language this will be an infinite loop because of the unterminated recursion. But in Haskell lazy evaluation does the Right Thing: it generates a two-element circular list.
To see how it works in practice, think about what happens at run-time. The usual "thunk" implementation of lazy evaluation represents an unevaluated expression as a data structure containing a function pointer plus the arguments to be passed to the function. When this is evaluated the thunk is replaced by the actual value so that future references don't have to call the function again.
When you take the first element of the list 'x' is evaluated down to a value (0, &y), where the "&y" bit is a pointer to the value of 'y'. Since 'y' has not been evaluated this is currently a thunk. When you take the second element of the list the computer follows the link from x to this thunk and evaluates it. It evaluates to (1, &x), or in other words a pointer back to the original 'x' value. So you now have a circular list sitting in memory. The programmer doesn't need to fix up the back-pointers because the lazy evaluation mechanism does it for you.
这不完全是你所要求的，并且与 Haskell 没有直接关系，而是 Bruce McAdam 的论文 关于总结 深入探讨了这个主题。 Bruce 的基本思想是使用名为 WRAP 的显式打结运算符，而不是在 Haskell、OCaml 和其他一些语言中自动完成的隐式打结。 这篇论文有很多有趣的例子，如果你对打结感兴趣，我想你会对这个过程有更好的感觉。
It's not quite what you asked for, and it's not directly related to Haskell, but Bruce McAdam's paper That About Wraps It Up goes into this topic in substantial breadth and depth. Bruce's basic idea is to use an explicit knot-tying operator called WRAP instead of the implicit knot-tying that is done automatically in Haskell, OCaml, and some other languages. The paper has lots of entertaining examples, and if you are interested in knot-tying I think you will come away with a much better feel for the process.