列表生成函数的惰性评估？
Lazy evaluation for list generating functions?
我目前正在阅读 Graham Hutton 的 Haskell 中的编程。
在 p.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 中的相等性检查以检查添加到因子列表中的每个新元素。
这怎么可能？
这不会使推断程序执行顺序变得更加困难吗？
您发现它 "shocking" 是因为您出乎意料。一旦你习惯了它......好吧，实际上它仍然会绊倒人。但过了一段时间，你最终会全神贯注。
Haskell 的工作原理是这样的：当您调用一个函数时，什么也没有发生！ 调用记录在某处，仅此而已。这几乎不需要任何时间。你的 "result" 实际上只是一个 "I owe you" 告诉计算机什么代码 运行 得到结果。请注意，这不是 整个 结果；只是它的第一步。对于整数之类的东西，是只有一步。但是对于列表来说，每个元素都是一个单独的步骤。
让我给你看一个更简单的例子：
print (take 10 ([1..] ++ [0]))
我和一位 C++ 程序员谈过，他 "shocked" 说这行得通。当然，“++[0]”部分必须先 "find the end of the list" 才能向其附加零？这段代码如何在有限的时间内完成？！
它 看起来像 这构建了 [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..] 是一个无限列表，所以第二行 always 适用。所以 [1..] ++ [0] 的 "result" 是 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 : []
你知道这是如何放松的吗？
现在，回到您的具体问题：(==) 运算符获取一对列表并遍历它们，逐个元素比较它们以确保它们相等。 一旦发现差异，它会立即中止并且returns 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
我将重点介绍这一点：
Doesn't this make way more difficult to reason about the order of execution of a program?
是的，但计算顺序在纯函数式编程中并不重要。例如：
(1 * 3) + (4 * 5)
问：先做哪个乘法？ A：我们不管，结果是一样的。即使是 C 编译器也可以在这里选择任何顺序。
(f 1) + (f 2)
问：先调用哪个函数？ A：我们不管，结果是一样的。在这里，C 编译器也可以选择任何顺序。然而，在 C 中，函数 f 可能有副作用，使得上面求和的结果取决于计算的顺序。在纯函数式编程中，没有副作用，所以我们真的不关心。
此外，惰性允许对任何函数定义进行语义保留扩展。假设我们定义
f x = e -- e is an expression which can use x
我们调用f 2。结果应与 e{2/x} 相同，即 e，其中每个（自由）出现的 x 已被 2 替换。这只是 "unfolding the definition"，就像在数学中一样。例如，
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 是否被定义（永远循环）。定义展开 总是 有效。
这实际上使得更容易推断程序行为。
不过，懒惰也有一些缺点。一个主要的问题是，虽然程序的语义（可以说）更简单，但估计程序的性能更难。要评估性能，您必须了解的不仅仅是最终结果：您需要拥有导致该结果的所有中间步骤的模型。特别是在高级代码中，或者当一些巧妙的优化开始时，这需要一些关于运行时实际工作方式的专业知识。
Doesn't this make way more difficult to reason about the order of execution of a program?
可能 - 至少，对于那些来自程序/面向对象范例的人来说。我在其他热切求值语言中使用迭代器和函数式编程做了很多工作，对我来说惰性求值策略不是学习的主要问题 Haskell。 （有多少次您希望您的 Java 日志语句在决定实际记录之前甚至不获取消息的数据？）
将 Haskell 中的所有列表处理视为在幕后编译为基于迭代器的实现。如果您在 Java 中使用 n 的可能因子作为 Iterator<Integer> 执行此操作，难道您不想在发现不是 [=12] 时立即停止吗=] 或 n？如果是这样，迭代器是否无限并不重要！
当你认真对待它时，执行的顺序并不重要。你真正关心的是：
- 结果的正确性
- 及时终止
- 任何副作用的相对顺序
现在，如果您有一个 "purely functional" 程序，就没有副作用。但那是什么时候发生的？除了直接 number/string 运算和元代码（即高阶函数）之外，几乎任何有用的东西都会有副作用。
幸运的是（或者不幸的是，取决于你问的是谁），我们有 monad 作为 设计模式 在 Haskell 中的目的（除其他事项外）控制评估顺序，因此控制副作用。
但即使不了解 monad 和所有这些东西，实际上推理执行顺序与在过程语言中一样容易。你只需要习惯它。
我目前正在阅读 Graham Hutton 的 Haskell 中的编程。
在 p.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
Falseis returned as soon as any factor other than one or the number itself is produced"
作为来自 C 和 Java 的人，我觉得这令人震惊。我原以为 factors 调用会先完成，将结果保存在堆栈中并将控制权传递给调用函数。但显然这里正在执行一个非常不同的程序：必须在 factors 中的列表理解上进行循环，并且正在检查 prime 中的相等性检查以检查添加到因子列表中的每个新元素。
这怎么可能？ 这不会使推断程序执行顺序变得更加困难吗？
您发现它 "shocking" 是因为您出乎意料。一旦你习惯了它......好吧，实际上它仍然会绊倒人。但过了一段时间，你最终会全神贯注。
Haskell 的工作原理是这样的：当您调用一个函数时，什么也没有发生！ 调用记录在某处，仅此而已。这几乎不需要任何时间。你的 "result" 实际上只是一个 "I owe you" 告诉计算机什么代码 运行 得到结果。请注意，这不是 整个 结果；只是它的第一步。对于整数之类的东西，是只有一步。但是对于列表来说，每个元素都是一个单独的步骤。
让我给你看一个更简单的例子：
print (take 10 ([1..] ++ [0]))
我和一位 C++ 程序员谈过，他 "shocked" 说这行得通。当然，“++[0]”部分必须先 "find the end of the list" 才能向其附加零？这段代码如何在有限的时间内完成？！
它 看起来像 这构建了 [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..] 是一个无限列表，所以第二行 always 适用。所以 [1..] ++ [0] 的 "result" 是 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 : []
你知道这是如何放松的吗？
现在，回到您的具体问题：(==) 运算符获取一对列表并遍历它们，逐个元素比较它们以确保它们相等。 一旦发现差异，它会立即中止并且returns 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
我将重点介绍这一点：
Doesn't this make way more difficult to reason about the order of execution of a program?
是的，但计算顺序在纯函数式编程中并不重要。例如：
(1 * 3) + (4 * 5)
问：先做哪个乘法？ A：我们不管，结果是一样的。即使是 C 编译器也可以在这里选择任何顺序。
(f 1) + (f 2)
问：先调用哪个函数？ A：我们不管，结果是一样的。在这里，C 编译器也可以选择任何顺序。然而，在 C 中，函数 f 可能有副作用，使得上面求和的结果取决于计算的顺序。在纯函数式编程中，没有副作用，所以我们真的不关心。
此外，惰性允许对任何函数定义进行语义保留扩展。假设我们定义
f x = e -- e is an expression which can use x
我们调用f 2。结果应与 e{2/x} 相同，即 e，其中每个（自由）出现的 x 已被 2 替换。这只是 "unfolding the definition"，就像在数学中一样。例如，
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 是否被定义（永远循环）。定义展开 总是 有效。
这实际上使得更容易推断程序行为。
不过，懒惰也有一些缺点。一个主要的问题是，虽然程序的语义（可以说）更简单，但估计程序的性能更难。要评估性能，您必须了解的不仅仅是最终结果：您需要拥有导致该结果的所有中间步骤的模型。特别是在高级代码中，或者当一些巧妙的优化开始时，这需要一些关于运行时实际工作方式的专业知识。
Doesn't this make way more difficult to reason about the order of execution of a program?
可能 - 至少，对于那些来自程序/面向对象范例的人来说。我在其他热切求值语言中使用迭代器和函数式编程做了很多工作，对我来说惰性求值策略不是学习的主要问题 Haskell。 （有多少次您希望您的 Java 日志语句在决定实际记录之前甚至不获取消息的数据？）
将 Haskell 中的所有列表处理视为在幕后编译为基于迭代器的实现。如果您在 Java 中使用 n 的可能因子作为 Iterator<Integer> 执行此操作，难道您不想在发现不是 [=12] 时立即停止吗=] 或 n？如果是这样，迭代器是否无限并不重要！
当你认真对待它时，执行的顺序并不重要。你真正关心的是：
- 结果的正确性
- 及时终止
- 任何副作用的相对顺序
现在，如果您有一个 "purely functional" 程序，就没有副作用。但那是什么时候发生的？除了直接 number/string 运算和元代码（即高阶函数）之外，几乎任何有用的东西都会有副作用。
幸运的是（或者不幸的是，取决于你问的是谁），我们有 monad 作为 设计模式 在 Haskell 中的目的（除其他事项外）控制评估顺序，因此控制副作用。
但即使不了解 monad 和所有这些东西，实际上推理执行顺序与在过程语言中一样容易。你只需要习惯它。