Funky haskell懒惰列表隐式递归

Question

在Haskell中,由于懒惰,您可以构建无限列表:

Prelude> let g = 4 : g
Prelude> g !! 0
4
Prelude> take 10 g
[4,4,4,4,4,4,4,4,4,4]

现在,当我尝试构建这样的列表时到底发生了什么？

Prelude> let f = f !! 10 : f
Prelude> f !! 0
Interrupted.
Prelude> take 10 f
[Interrupted.
Prelude>

该Interrupted.s的我按CTRL + C等待几秒钟后.它似乎陷入无限循环,但为什么会这样呢？

---

非Haskellers的解释:

该:操作是prepend:

Prelude> 4 : [1, 2, 3]
[4,1,2,3]

这一行:

Prelude> let g = 4 : g

说"让我们g通过预先4列入名单来构建清单g".当你要求第一个元素时,返回4,因为它已经存在.当你要求第二个元素时,它会查找4之后的元素.该元素将是列表的第一个元素g,我们刚刚计算(4),因此4返回.下一个元素是g我们再次计算的第二个元素,等等......

!!仅仅是索引到一个列表,所以这意味着在指数获得元素0的g:

Prelude> g !! 0
4

但是当我这样做时:

Prelude> let f = f !! 10 : f

有些东西会中断,因为要计算f你需要第11个元素的第一个元素,这个元素还不存在？我会期待一个例外,但不是一个无限循环......

Answer 1

在这种情况下,图片可以说出千言万语.

首先,记住cons((:)列表构造函数)是如何工作的.它是一对两件事:一个元素,一个列表尾部的引用(或者是另一个缺点,或者[]).

正如你所知,当你说[1, 2, 3],它只是(1:(2:(3:[])))或者的捷径1:2:3:[].如果您将每个缺点可视化为具有两个插槽的框,则此表达式如下所示:

????????  ????????  ????????  ??????
? 1 ? ???>? 2 ? ???>? 3 ? ???>? [] ?
????????  ????????  ????????  ??????

一圈

当你说g = 4 : g,你并没有真正构建一个"无限"列表时,你正在构建一个循环列表:g被定义为一个缺点,它的尾部引用简单地指向g 它自己:

????????????
? ???????? ?
?>? 4 ? ????
  ????????

这实际上无关懒惰,一切以自我参照:例如,你可以做同样的事情在(渴望)Common Lisp中使用类似语法'#1=(4 . #1#)(其中#1像g).

无论你说g !! 0,或者g !! 1000000000000,g永不:(!!)简单地到处跑,就地循环,为尽可能多的时间,你告诉它,直到它耗尽了自身,并返回元素4.

两个循环

当你说f = (f !! 10) : f,同样的事情发生 - 除了现在,元素槽包含一个不同的表达式4:

????????????
? ???????? ?
?>? ? ? ????
  ????????
    ?
    ? ?????????????
    ?>? (f !! 10) ?
      ?????????????

至关重要的是,这个子表达式也会引用回来f,就像尾巴一样:

 ????????????
 ? ???????? ?
??>? ? ? ????
?  ????????
?    ?
?    ? ?????????????
?    ?>? (f !! 10) ?
?      ?????????????
???????????

因此,当你要求时f !! n,(!!)首先会绕过顶部循环n次数,然后返回元素,就像它所做的那样g.然而,不是逃避循环,(f !! 10)而是重新进入循环,并且过程重复进行:围绕顶部循环10次,然后围绕底部循环,然后返回.

Answer 2

"现在还不存在"是不对的.我们尽量不考虑价值何时存在 - 指称性编程是关于永恒不变的价值观和方程式.

更具体地说,这段代码很好:

Prelude> let x = [(x !! 1) + 1, 3] in x
[4,3]

您可能认为这x !! 1还不存在.但这就是像GHC这样的实现如何运作.

构建列表时f,它构造一个内存中的对象("t​​hunk")来表示表达式(x !! 1) + 1.x尚未对评估进行评估.它将一个指向这个thunk的指针,加上一个指针指向3一个链表,并将其交给GHCi隐含的指针show.

现在,show列表实例必须逐个显示元素. show将要求("强制")thunk的评估(x !! 1) + 1,这导致该代码被"输入".根据(+)强迫(x !! 1) + 1力的定义,强制力x !! 1又强迫两件事:

• 的脊柱的列表(其缺点细胞)通过所述第二小区,并
• 第二个元素的值(第二个单元格的"car",以Lisp术语表示),因为(+)想要对该值进行操作.

第二个值现在存在 - 它是3.如果它是另一个thunk我们强迫它,等等.有关自引用容器的有趣视图,请参阅此博客文章.

现在,编译的GHC代码如何在另一个示例中检测到无限循环？当我们输入thunk时,我们需要记住稍后再回来并用最终值覆盖它.这就是"懒惰评估"而非"非严格语义"的含义,它阻止我们重复工作.

无论如何,作为进入thunk时的优化,GHC的运行时将首先用另一个称为"黑洞"的对象覆盖它.我们稍后会回来并用最终值覆盖黑洞.但是如果我们在这之前进入黑洞会发生什么呢？这意味着评估x需要首先评估x,这是一个无法解决的循环.所以进入黑洞会引发异常.

Answer 3

你为什么挂起是正确的 - 你创建了一个无法解决的循环依赖.计算当前元素需要一个后来的元素,在计算当前元素之前无法计算,等等,我们去的圈子.

至于它为什么不产生异常,尝试编译它而不是在GHCi中运行它:

$ ghc --make Loop.hs
$ ./Loop.exe
Loop.exe: <<loop>>

我假设这是一个NonTermination例外.Pff,停止问题？哈.

并非一切都按照您在GHCi中完成的方式或期望的方式运行.如果某些东西看起来很奇怪,请尝试编译一个小例子,看看它是否更有意义.例如,GHCi使用不同的类型默认规则会让我感到沮丧.