Haskell,无限列表上的折叠器

Question

我在读LYAH时遇到了一个问题.

这是我对无限列表中的foldr的想法:

foldr (:) [] [1..] = 1:2:...:**?:[]**

我认为GHCi在评估∞之前不知道它是列表:[].

但GHCi确实知道.

所以我认为它可以识别foldr(:) [] [无限列表] = [无限列表本身].

Prelude> [1..10] == (take 10 $ foldr (:) [] [1..])
True
Prelude> [1..] == (foldr (:) [] [1..])
Interrupted.

然而事实并非如此.

我想知道在评估∞:[]之前GHCi识别它是[1 ..]时实际发生了什么.

只需在评估之前输入推理？

Answer 1

我想知道GHCi [1..]在评估之前认识到实际发生了什么?:[].

GHCI并没有认识到这是[1...],这只是后果懒惰的评价.

foldr 实施方式如下:

foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

如果你喜欢写东西foldr (:) [] [1..],然后哈斯克尔并没有 evalautes这(直接),它只是要计算出店.

现在说你想要print (take 3 (foldr (:) [] [1..]))那个列表,然后Haskell被迫评估它,它将通过计算:

take 3 (foldr (:) [] [1..])
-> take 3 ((:) 1 (foldr (:) [] [2..]))
-> (:) 1 (take 2 (foldr (:) [] [2..]))
-> (:) 1 (take 2 ((:) 2 (foldr (:) [] [3..]))
-> (:) 1 ((:) 2 (take 1 (foldr (:) [] [3..])))
-> (:) 1 ((:) 2 (take 1 ((:) 3 (foldr (:) [] [4..]))))
-> (:) 1 ((:) 2 ((:) 3 (take 0 (foldr (:) [] [4..]))))
-> (:) 1 ((:) 2 ((:) 3 [])

所以它衍生出来[1, 2, 3],并且由于Haskell的懒惰,它对什么是不感兴趣foldr (:) [] [4..].即使该列表最终会停止,也不会对其进行评估.

如果计算类似的东西[1..] = foldr (:) [] [1..],那么Haskell将检查列表相等性,列表相等性定义为:

[] == [] = True
(x:xs) == (y:ys) = x == y && xs == ys
[] == (_:_) = False
(_:_) == [] = False

所以Haskell被迫放松右边的列表foldr,但它会一直这样做,直到它找到不相等的项目,或者列表中的一个到达结尾.但是因为每次元素都相等,并且两个列表都永远不会结束,所以它永远不会完成,因为它将评估它:

   (==) [1..] (foldr (:) [] [1..])
-> (==) ((:) 1 [2..])  ((:) 1 (foldr (:) [] [2..]))

它看到两者都是相等的,所以它递归地调用:

-> (==) ((:) 1 [2..])  ((:) 1 (foldr (:) [] [2..]))
-> (==) [2..] foldr (:) [] [2..])
-> (==) ((:) 2 [3..])  ((:) 2 (foldr (:) [] [3..]))
-> (==) [3..] foldr (:) [] [3..])
-> ...

但正如你所看到的,它永远不会停止评估.Haskell并不知道它foldr (:) [] [1..]等于[1..],它的目的是评估它,并且由于平等迫使它评估整个列表,它将陷入无限循环.

是的,可以在编译器中添加某个模式,这样就会foldr (:) [] x被替换为x,所以将来也许Haskell编译器可以返回True这些模式,但这不能从根本上解决问题,因为如果Haskell可以派生出这样的东西对于任何类型的函数(在这里(:),它将解决一个不可判定的问题,因此它是不可能的).