Haskell, 无限列表上的文件夹

Question

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

这是我对无限列表上的 foldr 的想法：

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

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

但是 GHCi 确实知道。

所以我认为它可以识别 foldr (:) [] [infinite list] = [infinite list itself]。

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

然而事实并非如此。

我想知道当 GHCi 在评估 ∞:[].

之前识别它是 [1..] 时实际发生了什么

只是在评估之前进行类型推断？

Answer 1

I want to know what actually happens when GHCi recognizes it is [1..] before evaluating ∞:[].

GHCi不识别它是[1...]，这只是惰性评估的结果。

foldr 实现为：

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

如果你写类似 foldr (:) [] [1..] 的东西，那么 Haskell 而不是 评估这个（直接），它只存储你想要计算的那个。

现在假设您想要 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被迫unwind右边的列表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 编译器可以 return True 对于这些，但这不会从根本上解决问题，因为如果 Haskell 可以为任何类型的函数派生出这样的东西（这里 (:)，那么它就解决了一个不可判定的问题，因此不可能。

Answer 2

Ghc（至少在理论上）不知道有限列表和无限列表之间的区别。它可以通过计算列表的长度来判断列表是有限的。如果你试图找到一个无限列表的长度，你会遇到麻烦，因为你的程序永远不会终止。

这个问题真的是关于惰性求值的。在像 C 或 python 这样的严格语言中，您需要在每一步都知道某些东西的全部价值。如果你想把一个列表的元素加起来，在开始之前你已经需要知道里面有什么东西，有多少。

Haskell中的所有数据具有以下形式：

一个完全已知的原始事物，如 int（不一定是整数）
数据类型构造函数及其参数，例如True、Left 7、(,) 5 'f'（与(5,'f')相同）或(:) 3 []

但在 Haskell 中，值有两种“形状”

已知并经过全面评估（如 C 或 python）
尚未评估 - 一个函数“thunk”，当您调用时将 return 以更评估的方式计算值

在Haskell中有一个概念叫做weak head normal form其中：

任何原语都被完全评估
对于任何有构造函数的东西，构造函数是已知的，参数可能还没有被评估。

让我们看看foldr (:) [] [1..]的评估过程。首先定义foldr

foldr f a [] = a
foldr f a (x:xs) = f x (foldr xs)

现在 foldr (:) [] [1..] 是什么？

foldr (:) [] [1..]

看来只是个咚咚。我们对此一无所知。所以让我们把它评估成WHNF。首先，我们需要将参数 [1..]（实际上是 enumFrom 1）转换为 WHNF，以便我们可以对其进行模式匹配：

foldr (:) [] (1:[2..])

现在我们可以评估 foldr:

(:) 1 (foldr [] [2..])
1 : (foldr [] [2..])

因此我们已经计算了列表的第一个元素，而无需查看其整个无限长度。同样我们可以算出第二个元素等等。

那么如果我们 [1..] == [1..] 会发生什么？那么列表的 == 的定义是（省略三种情况）

(x:xs) == (y:ys) = x == y && xs == ys

所以尝试减少到 WHNF 我们得到：

[1..] == [1..]
(1 == 1) && ([2..] == [2..])
True && ([2..] == [2..])
[2..] == [2..]
... and so on

因此我们一直继续下去，永远不会得到一个构造函数，我们可以用它来模式匹配（即检查）结果。

请注意，我们可以取消 True && ...，因为 && 的定义不会查看其第二个参数：

True && x = x
False && _ = False

如果我们用完整的四向真值 table 定义 &&，程序运行内存不足的速度会比运行快得多（前提是编译器没有做任何聪明的事情）上面的地方你会运行失去耐心（或者宇宙射线击中你的 ram 并使你的程序 return False）

Haskell, 无限列表上的文件夹

Haskell, foldr on infinite list

haskell

type-inference

fold