12

我已经定义了无限列表的无限列表pathCounts和有限列表的无限列表pathCounts'：

import Data.Function (fix)

nextRow xs = fix $ \ys -> zipWith (+) xs (0:ys)

pathCounts = repeat 1 : map nextRow pathCounts
pathCounts' = map (take 100) pathCounts

进入 ghci，如果我根本没有评估任何一个，我可以:p成功使用任何一个：

ghci> :p pathCounts
pathCounts = (_t1::[[Integer]])
ghci> :p pathCounts'
pathCounts' = (_t2::[[Integer]])

但是，如果我部分评估pathCounts'，然后在仍然成功的同时:p冻结：pathCountspathCounts'

ghci> head . head $ pathCounts'
1
ghci> :p pathCounts'
pathCounts' = (1 : (_t4::[Integer])) : (_t5::[[Integer]])
ghci> :p pathCounts
^CInterrupted.

我希望:p pathCounts打印与 相同的:p pathCounts'内容，因为我只对其进行了部分评估。为什么它不起作用？

4

1 回答 1

8

我希望:p pathCounts打印与 相同的:p pathCounts'内容，因为我只对其进行了部分评估。

啊，但这就是有趣的地方！事实上，您已经全面评估了pathCounts. 让我们举一个稍微小一点的例子来简化讨论：

> let v = repeat 1 :: [Int]
> head v
1
> :p v
^C

我声称经过充分评估后head v，实际上v也得到了充分评估。这是因为，在内存中，v是一个循环单链表。因此，如果您已经评估到足以知道第一个元素，那么就没有什么可以评估的了！

结果是，当您要求:print它时，GHC 会适当地尝试构造一个表示结构的所有评估部分的字符串——显然不能，因为它永远不会停止遍历。（:p根本没有办法在结构中表示共享。）

相比：

> let x = 1 :: Int; v = (x, x)
> fst v
1
> :p v
(1,1)

尽管您只要求评估 的第一部分v，但实际上所有的v都已在此处评估，因此:p将其全部打印出来——并不表示第一部分和第二部分之间存在共享。

现在，怎么pathCounts'没有同样的问题？好吧，事情是这样的，虽然map f (repeat x) = repeat (f x)是一个指称正确的方程，但在 Haskell 的 GHC 实现中，这个方程在操作上并不健全——而且:p完全是关于操作语义的，并且对指称语义嗤之以鼻。特别是，map不（不能）观察到 ; 中存在的共享repeat x。因此它产生一个非循环无限列表。由于map f (repeat x)共享较少，因此强制部分map f (repeat x)不会导致内存中的表示被完全评估。

于 2015-06-25T17:26:07.053 回答