列表生成函数的懒惰评估？
我目前正在阅读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]
作者接着解释如何
“决定一个数不是素数并不要求函数素数产生所有的因素，因为在懒惰的评估中，一旦产生除了一个或数字本身以外的任何因素， False就返回”
作为来自C和Java的人，我觉得这很令人震惊。 我曾预期这些factors会首先完成，将结果保存在堆栈中并将控制权交给调用函数。 但显然这里正在执行一个非常不同的程序：在factors必须有一个遍历列表理解的循环，并且正在检查添加到因子列表中的每个新元素的prime相等检查。
这怎么可能？ 这难道不会更难以推断程序的执行顺序吗？
你会发现它“令人震惊”，因为你并不期待它。 一旦你习惯了它......好吧，实际上它仍然让人们绊倒。 但过了一段时间，你最终会围绕它思考。
Haskell如何工作是这样的：当你调用一个函数时，没有任何反应！ 电话记录在某处，这就是全部。 这几乎不需要时间。 你的“结果”实际上只是一个“我欠你”，告诉计算机运行什么代码来获得结果。 不是全部结果，请关注你; 只是它的第一步。 对于像整数这样的东西，只有一个步骤。 但是对于一个列表，每个元素都是一个单独的步骤。
让我给你展示一个更简单的例子：
print (take 10 ([1..] ++ [0]))
我曾与一位C ++程序员交谈过，他对此感到“震惊”。 当然，“ ++[0] ”部分必须“找到列表的末尾”，才能将零附加到它上面？ 这段代码如何在有限的时间内完成？！
它看起来像这样构建了[1..] （在无限列表中），然后++[0]扫描到该列表的末尾并插入一个零，然后从前10个元素中take 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
我将专注于这一点：
这难道不会更难以推断程序的执行顺序吗？
是的，但评估顺序在纯功能编程中并不重要。 例如：
(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 （永远循环）。 定义展开始终有效。
这实际上使得对程序行为的推理变得更简单。
虽然有一些懒惰的缺点。 主要的一点是，虽然程序的语义（可以说）更简单，但估计程序的性能却更困难。 为了评估绩效，你必须了解最终的结果：你需要有一个导致这个结果的所有中间步骤的模型。 特别是在高级代码中，或者当一些聪明的优化开始时，这需要一些运行时实际工作方面的专业知识。
这难道不会更难以推断程序的执行顺序吗？
可能 - 至少对于那些来自程序/ OO范式的人来说。 我在其他热衷于评估语言的迭代器和函数式编程方面做了很多工作，对我来说懒惰的评估策略并不是学习Haskell的主要问题。 （你有多少次希望你的Java日志语句在决定实际登录之前甚至不会获取该消息的数据？）
想想Haskell中的所有列表处理，就好像它已被编译为基于迭代器的实现。 如果你在Java中使用n作为Iterator<Integer>给出的可能因素，那么当你发现一个不是1或n你不想停止吗？ 如果是这样，迭代器是否无限无关紧要！
当你仔细考虑时，执行顺序并不重要。 你真正关心的是：
现在，如果你有一个“纯粹功能”的程序，就没有副作用。 但是这是什么时候发生的？ 除了直接数字/字符串运算和元编码（即高阶函数）之外，几乎任何有用的东西都会产生副作用。
幸运的是（或者不幸的是，取决于你问的对象），我们把Hasad作为Haskell中的设计模式，用来控制评估顺序，从而控制副作用。
但即使没有了解monad和所有这些东西，它实际上就像在程序语言中一样容易推断执行的顺序。 你只需要习惯它。
链接地址: http://www.djcxy.com/p/47683.html