为什么我对自我引用懒惰序列的直觉是错误的？

Question

在Haskell中,我可以在GHCI中编写一个自引用序列,如下所示:

?> let x = 1:map (+1) x
?> take 5 x

产生:

[1,2,3,4,5]

然而,我对懒惰评估的直觉说这应该在扩展期间发生

let x = 1:map (+1) x
1:2:map (+1) x
1:2:map (+1) [1, 2] <-- substitution
1:2:2:3:map (+1) x
1:2:2:3:map (+1) [1, 2, 2, 3] <-- substitution
1:2:2:3:2:3:3:4:map (+1) x
...

这显然不是正在发生的事情.我可以在正确答案中看到模式.我们只是在无限流中一次移动列表中的一个元素.我认识的模式,我可以在代码中应用它.然而,它与我的懒惰评估的心理模型不符.感觉有点"神奇".我的直觉在哪里错了？

Answer 1

请记住只用其定义替换某些东西.因此,无论何时扩展x,都应该替换1 : map (+1) x,而不是它的"当前值"(无论这意味着什么).

我将重现杰弗弗的想法,但要适当尊重懒惰.

x = 1 : map (+1) x

take 5 x
= take 5 (1 : map (+1) x)                                 -- x
= 1 : take 4 (map (+1) x)                                 -- take
= 1 : take 4 (map (+1) (1 : map (+1) x)                   -- x
= 1 : take 4 (2 : map (+1) (map (+1) x))                  -- map and (+)
= 1 : 2 : take 3 (map (+1) (map (+1) x))                  -- take
= 1 : 2 : take 3 (map (+1) (map (+1) (1 : map (+1) x)))   -- x
= 1 : 2 : take 3 (map (+1) (2 : map (+1) (map (+1) x)))   -- map and (+)
= 1 : 2 : take 3 (3 : map (+1) (map (+1) (map (+1) x)))   -- map and (+)
= 1 : 2 : 3 : take 2 (map (+1) (map (+1) (map (+1) x)))   -- take

等等.

练习自己以这种方式完成评估(这是非常有用的).

注意map随着列表的增长,我们如何开始构建一个s 链.如果你只是print x,你会看到一段时间后输出开始变慢; 这就是为什么.有一种更有效的方式,留作练习(并且[1..]作弊:-).

注意,这仍然比实际发生的情况稍微懒散一点. map (+1) (1 : ...)评估为(1+1) : map (+1) ...,并且只有在实际观察到数字时,才会通过打印或比较它来进行添加.

Ness会在这篇文章中发现错误吗？看到评论和他的答案.

Answer 2

这是发生了什么.懒惰是非严格+ 记忆(thunk).我们可以通过命名在强制表达式时出现的所有临时数据来证明这一点:

?> let x  = 1  : map (+1) x
   >>> x  = a1 : x1                             -- naming the subexpressions
       a1 = 1
       x1 = map (+1) x 

?> take 5 x 
==> take 5 (a1:x1)                              -- definition of x
==> a1:take 4 x1                                -- definition of take
          >>> x1 = map (1+) (1:x1)              -- definition of x
                 = (1+) 1 : map (1+) x1         -- definition of map
                 = a2     : x2                  -- naming the subexpressions
              a2 = (1+) 1                        
              x2 = map (1+) x1  
==> a1:take 4 (a2:x2)                           -- definition of x1
==> a1:a2:take 3 x2                             -- definition of take
             >>> x2 = map (1+) (a2:x2)          -- definition of x1
                    = (1+) a2 : map (1+) x2     -- definition of map
                    = a3      : x3              -- naming the subexpressions
                 a3 = (1+) a2                    
                 x3 = map (1+) x2  
==> a1:a2:take 3 (a3:x3)                        -- definition of x2
==> a1:a2:a3:take 2 x3                          -- definition of take
                >>> x3 = map (1+) (a3:x3)       -- definition of x2
.....

结果流中的元素a1:a2:a3:a4:...均指其前身:a1 = 1; a2 = (1+) a1; a3 = (1+) a2; a4 = (1+) a3; ....

因此它相当于x = iterate (1+) 1.如果没有数据的共享和通过反向引用(通过存储的存储器启用)的重用,它将等同于x = [sum $ replicate n 1 | n <- [1..]]从根本上效率较低的计算(O(n ²)而不是O(n)).

我们可以解释共享与非共享

fix g = x where x = g x        -- sharing fixpoint
x = fix ((1:) . map (1+))      --  corecursive definition

_Y g = g (_Y g)                -- non-sharing fixpoint
y = _Y ((1:) . map (1+))       --  recursive definition

试图y在GHCi的提示下打印显示随着进展的进展而显着放缓.打印x流时没有减速.

(有关类似示例,另请参阅/sf/answers/1468468011/).