"打结"的解释

在阅读哈斯克尔有关的东西,我有时会遇到表达"绑结",我想我明白了什么是这样,而不是如何.

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

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

假设您想要一个包含元素"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'值.所以你现在有一个循环列表坐在内存中.程序员不需要修复后向指针,因为懒惰的评估机制会为你做这件事.

这并不是你所要求的,而且它与Haskell没有直接关系,但是Bruce McAdam的论文"关于Wraps It Up"在很大程度上涉及到这个主题.Bruce的基本思想是使用一个名为WRAP 的明确的结点操作符,而不是在Haskell,OCaml和其他一些语言中自动完成的隐式结点操作.这篇论文有很多有趣的例子,如果你对打结感兴趣,我想你会对这个过程有更好的感觉.