列表解析中的条款

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

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

操作上，他们的分享行为在不同的call-by-需要评估。 jcast已经解释了为什么，但我想添加一个不需要明确排除列表理解的快捷方式。规则是：在语法在那里可以依赖于一个变量x位置任意表达式将每个变量x绑定到一个值重新计算时间，即使表达实际上并不取决于x。

在你的情况，在第一定义，x是在cp xss出现的位置范围，因此cp xss将重新评估每个元素的xsx。在第二个定义cp xss出现在x的范围之外，因此它将被计算一次。

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

• 编译器并不需要遵守的call-by-需要评估，只有指称语义的操作语义。所以它可能会根据上述规则计算比预期更少的次数（浮出）或更多次（浮动）。

• 这不是一般的事实，更多的共享是更好的。例如，在这种情况下，它可能不会更好，因为cp xss的规模增长速度与首先计算它的工作量一样快。在这种情况下，从内存读取值的成本可能会超过重新计算值（由于缓存层次结构和GC）。

Answer 2

好了，天真的脱糖会：

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确实有一个优化遍浮昂贵的计算出这样的循环，所以它可以在第一版本自动转换到第二。你的书上说的第二个版本“保证”来计算cp xss值只有一次，因为，如果表达式是计算价格昂贵，编译器一般会很犹豫，它内联（转换的第二个版本返回到第一）。