Haskell中列表理解的效率

Question

我一直在学习Haskell，我做了一些统计函数，这些函数可以用于Int或Float类型的列表
以下是两个示例：

mean :: (Real a, Floating b) => [a] -> b
mean xs = realToFrac (sum xs) / genericLength xs

sumOfSquares :: (Real a, Floating b) => [a] -> b
sumOfSquares xs = [(mean xs - realToFrac x) ^^ 2 | x <- xs]

然而，我现在想知道我是否可以通过以不同的方式编写SumOfSquares来改进运行时。像这样：

sumOfSquares xs = [(m - realToFrac x) ^^ 2 | x <- xs] where m = mean xs

或者像这样：

sumOfSquares xs = [(m - realToFrac x) ^^ 2 | x <- xs, let m = mean xs]

我不知道哈斯克尔在屏幕后面是怎么处理的。在原始版本中，计算机是否为xs中的每个条目计算平均xs？我想Haskell不会在背景中优化理解。我错了吗？

Answer 1

脱脂确实会产生不同的代码。这里有三种实现。我将展示如果没有列表理解，它们中的每一个会是什么样子。

-- With no let / where
sumOfSquares xs = [(mean xs - realToFrac x) ^^ 2 | x <- xs]
sumOfSquares xs = map (\x -> (mean xs - realToFrac x) ^^ 2) xs

-- With let inside the comprehension
sumOfSquares xs = [(m - realToFrac x) ^^ 2 | x <- xs, let m = mean xs]
sumOfSquares xs = map (\x -> let m = mean xs in (m - realToFrac x) ^^ 2) xs

-- With where outside the comprehension
sumOfSquares xs = [(m - realToFrac x) ^^ 2 | x <- xs] where m = mean xs
sumOfSquares xs = map (\x -> (m - realToFrac x) ^^ 2) xs where m = mean xs

所以前两者基本相当。如果你有世界上最简单的编译器（或者你关闭优化），你会得到效率相当低的代码，每次迭代都会重新计算平均值。第三种方法完全避免了这种情况，实际上是将计算放在的块之外。它不能保证值不会在每一步都被重新计算（Haskell可以自由地计算它选择的东西，只要结果的行为等同于懒惰的计算），但是如果你的编译器不是很聪明，它确实会提高几率。

然而，实际上，GHC（和大多数其他编译器）将执行所谓的浮点优化。基本上，如果它看到一个let块，它可以在重复计算之外移动，它可以自由地这样做，因为这样做不会产生任何可能的副作用。一般来说，GHC将采用以下形式的表达式

\x -> let y = something in f x y

并将其转换为

let y = something in \x -> f x y

这种优化是允许的，只要x在某物中不显示为自由变量，并且大多数编译器对此相当聪明，所以您不应该有太多的担心。

关于GHC执行的许多常见优化，有一个极好的StackOverflow答案，这个答案的部分灵感来源于此。如果你想更多地了解Haskell的效率，我建议你去看看。