为什么 Haskell 列表理解比循环更快

Question

我是 Haskell 菜鸟。在试验循环和列表理解时，我发现列表理解比循环更快。 Lisp 理解使用求幂并且仍然更快。为什么？

lg :: Int -> Int -> Int -> Int
lg s e a =
  if s < e
  then
  if even s
  then
    lg (s+1) e (a+1)
  else
    lg (s+1) e (a*2)
  else
    a

loopGrowth :: Int -> Int
loopGrowth x = lg 0 x 0

calcGrowth :: Int -> Int
calcGrowth y =
  last (take (y+1) (tail (join [ [2 ^ x - 2 ,2 ^ x - 1] | x <- [1..50] ])))

Answer 1

首先是一些风格建议：

lg s e a
  | s >= e     = a
  | even s     = lg (s+1) e (a+1)
  | otherwise  = lg (s+1) e (a*2)

关于您的问题：lg 并不是真正的循环。这是一个尾递归函数，但仅此一项在 Haskell 中并没有说明什么。阻碍的主要因素是惰性：如果累加器仅在 thunk 维度中累积，而不是它们的值，那么惰性只会增加大量的开销而没有任何可用性增益。

防止这种情况的一个简单方法是严格评估参数，

{-# LANGUAGE BangPatterns     #-}

lg' s e !a
  | s >= e     = a
  | even s     = lg' (s+1) e (a+1)
  | otherwise  = lg' (s+1) e (a*2)

然而，由于这些问题以及 conciseness/modularity/...，最好不要编写尾递归函数，而是使用更高级别的工具——列表理解本身通常是在性能方面没有那么好，但是如果你用通用折叠等方式表达你的算法，你可以使用性能更高的数据结构，例如未装箱的向量，而你的代码几乎没有变化。

Answer 2

除了 @leftaroundabout 提到的更复杂的 thunk 问题，我可以想到两个 algorithmic 列表理解可能比你想象的更有效的原因：

由于懒惰，实际上只评估了列表元素中的一个。所以只执行一次求幂。
Haskell 的 ^ 比循环中的简单乘法更聪明：它在内部使用除以 2 以大大减少所需的乘法次数。例如。 x^8 变为 "essentially" let x2 = x*x; x4 = x2*x2 in x4*x4。（编辑：正如@dfeuer 指出的那样，这被称为 "fast exponentiation" 或 "exponentiation by squaring"。）

为什么 Haskell 列表理解比循环更快

Why Haskell list comprehension is faster than loop

haskell