列表理解中的 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]]

根据 Thinking Functionally With Haskell（第 92 页），第二个版本是 "a more efficient definition...[which] guarantees that cp xss is computed just once,"，尽管作者从未解释过原因。我还以为他们是等价的。

Answer 1

嗯，天真的脱糖是：

cp [] = [[]]
cp (xs:xss) = concatMap (\x -> concatMap (\ ys -> [ x:ys ]) (cp xss)) xs
----------------------------------------------
cp [] = [[]]
cp (xs:xss) = let yss = cp xss in concatMap (\x -> concatMap (\ ys -> [ x:ys ]) yss) xs

如您所见，在第一个版本中，调用 cp xss 在 lambda 中。除非优化器移动它，否则这意味着每次调用函数 \x -> concatMap (\ ys -> [ x:ys ]) (cp xss) 时都会重新评估它。通过浮动它，我们避免了重新计算。

同时，GHC 确实有一个优化通道，可以像这样将昂贵的计算从循环中浮出，因此它可能会自动将第一个版本转换为第二个版本。你的书说第二个版本 'guarantees' 只计算一次 cp xss 的值，因为如果表达式的计算成本很高，编译器通常会非常犹豫是否内联它（将第二个版本转换回第一个）。

Answer 2

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

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

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

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

编译器不需要遵守按需求值的操作语义，只需要遵守指称语义。因此，根据上述规则，它可能会比您预期的计算次数更少（浮动）或更多次（浮动）。
并不是说分享越多越好。例如，在这种情况下，它可能不会更好，因为 cp xss 的大小增长与最初计算它所花费的工作量一样快。在这种情况下，从内存中读回值的成本可能超过重新计算值的成本（由于缓存层次结构和 GC）。

列表理解中的 where 子句

where clauses in list comprehensions

haskell

list-comprehension