列表生成函数是否支持惰性求值？
列表生成函数是否支持惰性求值？
我正在阅读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]
作者随后解释说:
“判断一个数字不是质数，并不需要prime函数产生它的所有因子，因为在惰性求值下，只要任何一个不是1或本身的因数的因子产生了，就会返回结果False。”
作为一个来自C和Java的人，我感到震惊。我本来期望调用先完成，将结果保存在堆栈中，并将控制权传递给调用函数。但显然，这里正在执行一个非常不同的程序：在列表推导中必须循环，而中的相等性检查也将在添加到因子列表的每个新元素中被检查。
这怎么可能？
这难道不使得推理程序执行顺序变得更加困难吗？
我将重点讨论这一点：
这难道不让我们更难推理程序的执行顺序吗？
是的，但在纯函数式编程中，评估顺序并不那么重要。例如：
(1 * 3) + (4 * 5)
问：哪一个乘法先执行？回答：我们不关心，结果是一样的。即使C编译器可以在这里选择任何顺序。
(f 1) + (f 2)
问：哪个函数调用先执行？回答：我们不关心，结果是一样的。在这里，C编译器也可以选择任何顺序。但是，在C中，函数f可能具有副作用，从而使上述总和的结果取决于评估的顺序。在纯函数式编程中，没有副作用，所以我们真的不关心。
另外，惰性计算允许语义保留任何函数定义的扩展。假设我们定义
f x = e -- e is an expression which can use x
我们调用f 2。结果应该与e{2/x}相同，即e将每个（自由的）x出现的位置替换为2。这就像在数学中"展开定义"。例如：
f x = x + 4 -- f 2 ==> 2 + 4 ==> 6
但是，如果我们调用f(g 2)。惰性计算使这等效于e{g 2/x}。同样的，在数学中。例如：
f x = 42 g n = g (n + 1) -- infinite recursion
然后，我们仍然有f(g 2)=42 {g 2/x}=42，因为x没有被使用。我们不必担心g 2是否已定义（无限循环）。定义展开始终有效。
这实际上使推理程序行为变得更加简单。
懒惰也有一些不足之处。其中一个主要的不足之处是，虽然程序的语义（可以说）更简单，但估计程序的性能更难。为了评估性能，您必须了解不仅最终结果是什么，还需要了解通向该结果的所有中间步骤的模型。特别是在高级代码中，或当某些聪明的优化发挥作用时，这需要一些关于运行时实际工作方式的专业知识。
你觉得它很“惊人”是因为你没有预料到它。一旦你习惯了... 好吧，实际上它仍然会让人迷惑。但过一段时间，你最终会理解。
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