为什么产品 [0..] 的计算结果不是 0 "instantly"？

Question

我试图理解懒惰。因为 0 乘以任何数都是 0，所以 product [0..] 不应该计算为 0 吗？我也尝试 foldl (*) 1 [0..]，并将我自己的产品定义为

myProduct 0 _ = 0
myProduct _ 0 = 0
myProduct a b = a*b

为什么不在找到 0 后立即停止折叠？

Answer 1

因为乘法运算符不知道它正在被链接，并且折叠函数不知道乘法运算符对任何参数的特定行为。通过这种组合，它需要用尽列表才能完成折叠。事实上，foldl doesn't work at all on infinite lists. foldr确实是这个原因，因为它可以从链表的头部扩展功能。

foldl (*) 1 [0..] -> (((..(((1*0)*1)*2)*3....)*inf

永远找不到 foldl 情况下的最外层乘法，因为列表是无限的。因此它不能沿着链得出结果为零的结论。它可以并且确实会计算列表中的乘积，并且该乘积恰好保持为零，但它不会终止。如果您改用 scanl，您可以看到这些中间产品。

foldr (*) 1 [0..] -> 0*(1*(2*(3*((...((inf*1)))...)))

立即找到 foldr 情况下的最外层乘法，因为列表的其余部分实际上是作为惰性 thunk 留下的。它只运行一步：

foldr (*) 1 [0..] -> 0*(foldr (*) 1 [1..])

因此，如果第一个参数为零，那么因为您的自定义乘法运算符 myProduct 在第二个参数中并不严格，所以 foldr myProduct 1 [0..] 可以终止。

附带说明一下，prelude product 函数仅限于有限列表（并且可以使用 foldl 实现）。即使它使用 foldr，它也可能不会快捷，因为标准的乘法运算符是严格的；在乘积既不是零也不是链式的常见情况下，否则计算量很大。

-- sum and product compute the sum or product of a finite list of numbers.

sum, product     :: (Num a) => [a] -> a
sum              =  foldl (+) 0  
product          =  foldl (*) 1

此外，它不使用foldr也是有原因的；正如我们在 expansions 和 scanl 函数中看到的那样，左边的折叠可以在它们使用列表时进行计算。正确的折叠，如果运算符没有快捷方式，需要构建一个与列表本身一样大的表达式才能开始计算。这种差异是因为在严格情况下是最内层的表达式开始计算，而产生结果的是最外层的表达式，从而允许惰性情况。 Haskell wiki 中的 Lazy vs. non-strict 可能比我解释得更好，甚至提到您用来描述 myProduct 中的快捷方式的模式匹配可以是严格的。

Answer 2

如果你切换前两行：

myProduct _ 0 = 0
myProduct 0 _ = 0
myProduct a b = a*b

第二个参数将始终在第一个参数之前计算，无限文件夹将不再起作用。

因为不可能定义一个对两个参数都惰性工作的 myProduct（如果第一个为 0 则不评估第二个，如果第二个为 0 则不评估第一个）也许我们最好有* 总是计算它的两个参数。

Answer 3

你可以这样拥有：

myproduct xs = foldr op id xs 1
  where
    op x r acc = if x==0 then 0 else acc `seq` r (acc*x)

这是将左边的数字相乘的右折叠，以常数 space 运算，并在遇到 0 时立即停止。

为什么产品 [0..] 的计算结果不是 0 "instantly"？

Why doesn't product [0..] evaluate to 0 "instantly"?

haskell

lazy-evaluation