列表推导中的条款

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的功能性思考(p.92),第二个版本是"更有效的定义...... [保证cp xss只计算一次",尽管作者从未解释过为什么.我原以为他们是等同的.

Answer 1

当然,这两个定义在它们表示相同值的意义上是等价的.

在操作上,它们在按需调用评估中的共享行为方面存在差异.jcast已经解释了为什么,但是我想添加一个不需要明确地去除列表理解的快捷方式.规则是:x每次将变量x绑定到值时,语法上处于可依赖于变量的位置的任何表达式都将被重新计算,即使表达式实际上不依赖于该表达式x.

在你的情况下,在第一个定义,x是在在位置范围cp xss出现,所以cp xss将重新评估每个元素x的xs.在第二个定义cp xss出现在范围之外,x因此它将只计算一次.

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

• 编译器不需要遵循按需调用评估的操作语义,只需遵循指称语义.因此,根据上述规则,它可能会比您预期的更少次数(浮动)或更多次(浮动).

• 一般而言,更多共享更好是不正确的.在这种情况下,例如,它可能不会更好,因为它的大小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一次的值,因为如果表达式的计算成本很高,编译器通常会非常犹豫地内联它(将第二个版本转换回第一个版本).