haskell - 列表推导式中的 where 子句

Question

下面两个公式有什么区别？

cp [] = [[]]
cp (xs:xss) = [x:ys | x <- xs, ys <- cp xss]
----------------------------------------------
cp [] = [[]]
cp (xs:xss) = [x:ys | x <- xs, ys <- yss]
              where yss = cp xss

示例输出:cp [[1,2,3],[4,5]] => [[1,4],[1,5],[2,4],[2,5 ],[3,4],[3,5]]

根据用 Haskell 进行函数式思考(第 92 页)，第二个版本是“一个更有效的定义......[它]保证 cp xss 仅计算一次”，尽管作者从不解释为什么。我本以为它们是等价的。

Answer 1

当然，这两个定义在表示相同值的意义上是等效的。

在操作上，它们在按需评估下的共享行为有所不同。 jcast 已经解释了原因，但我想添加一个不需要显式对列表理解进行脱糖的快捷方式。规则是:每次将变量 x 绑定(bind)到一个值时，任何在语法上可能依赖于变量 x 的表达式都会被重新计算，即使该表达式实际上并不依赖于x。

在您的情况下，在第一个定义中，x 位于 cp xss 出现位置的范围内，因此 cp xss 将是重新评估 xs 的每个元素 x。在第二个定义中，cp xss 出现在 x 的范围之外，因此只会计算一次。

然后适用通常的免责声明，即:

• 编译器不需要遵守按需调用评估的操作语义，只需遵守指称语义。因此，根据上述规则，它计算的次数可能比您预期的更少(浮出)或多次(浮入)。

• 一般来说，分享越多越好的说法并不正确。例如，在这种情况下，它可能不会更好，因为 cp xss 的大小与最初计算它所需的工作量一样快。在这种情况下，从内存读回值的成本可能会超过重新计算该值的成本(由于缓存层次结构和 GC)。