haskell - 列表生成函数的延迟评估？

Question

我目前正在阅读 Graham Hutton 的《Haskell 编程》。

在第 40 页中，提出了一个玩具素数测试:

factors :: Int -> [Int]
factors n = [x | x <- [1..n], n `mod` x == 0]

prime :: Int -> Bool
prime n = factors n == [1,n]

然后作者继续解释如何

"deciding that a number is not prime does not require the function prime to produce all of its factors, because under lazy evaluation the result False is returned as soon as any factor other than one or the number itself is produced"

作为一个来自 C 和 Java 的人，我觉得这很令人震惊。我本来期望 factors首先调用完成，将结果保存在堆栈中并将控制权传递给调用函数。但显然这里正在执行一个非常不同的程序: factors 中的列表理解必须有一个循环。和 prime 中的相等检查正在检查添加到因子列表中的每个新元素。

这怎么可能？
这不是更难推理程序的执行顺序吗？

Answer 1

你会觉得它“令人震惊”，因为你没有预料到它。一旦你习惯了它......好吧，实际上它仍然会绊倒人们。但过了一会儿，你最终把你的想法包围了。

Haskell 的工作原理是这样的:当你调用一个函数时，什么也没有发生!电话在某处被记录下来，仅此而已。这几乎不需要任何时间。你的“结果”实际上只是一个“我欠你的”，告诉计算机要运行什么代码才能得到结果。请注意，不是全部结果；只是它的第一步。对于像整数这样的东西，只有一步。但是对于一个列表，每个元素都是一个单独的步骤。

让我给你看一个更简单的例子:

print (take 10 ([1..] ++ [0]))

我与一位 C++ 程序员交谈过，他对这种方法感到“震惊”。当然，“ ++[0]”部分必须“找到列表的末尾”才能将零附加到它上面？这段代码如何在有限时间内完成？!

看起来像这样构建 [1..] (在无限列表中)，然后是 ++[0]扫描到此列表的末尾并插入一个零，然后 take 10只剪掉前 10 个元素，然后打印。当然，这将花费无限的时间。

所以这就是实际发生的事情。最外层的函数是 take ，所以这就是我们开始的地方。 (没想到吧？) take 的定义是这样的:

take 0 (   _) = []
take n (  []) = []
take n (x:xs) = x : (take (n-1) xs)

很明显 10 != 0，所以第一行不适用。所以第二行或第三行都适用。所以现在 take看着 [1..] ++ [0]查看它是空列表还是非空列表。

这里最外层的函数是 (++) .它的定义看起来类似于

(  []) ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

所以我们需要弄清楚哪个方程适用。左边的参数要么是一个空列表(第一行适用)，要么不是(第二行适用)。好吧，因为 [1..]是一个无限列表，第二行总是适用。所以 [1..] ++ [0]的“结果”是 1 : ([2..] ++ [0]) .如您所见，这并没有完全执行；但它执行得足够远，足以说明这是一个非空列表。这就是 take关心。

take 10 ([1..] ++ [0])
take 10 (1 : ([2..] ++ [0]))
1 : take 9 ([2..] ++ [0])
1 : take 9 (2 : ([3..] ++ [0]))
1 : 2 : take 8 ([3..] ++ [0])
1 : 2 : take 8 (3 : ([4..] ++ [0]))
1 : 2 : 3 : take 7 ([4..] ++ [0])
...
1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : take 0 ([11..] ++ [0])
1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : []

你看到这是如何展开的吗？

现在，回到您的具体问题: (==)运算符获取一对列表并遍历它们，逐个元素地比较它们以确保它们相等。一旦发现差异，它立即中止并返回 false:

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

如果我们现在尝试，比如说， prime 6 :

prime 6
factors 6 == [1,6]
??? == [1,6]
1 : ??? == [1,6]
??? == [6]
2 : ??? == [6]
False