任务：“对前 15,000,000 个偶数求和。”

Haskell:

nats = [1..] :: [Int]
evens = filter even nats :: [Int]

MySum:: Int
MySum= sum $ take 15000000 evens

...but MySum需要很长时间。更准确地说，比 C/C++ 慢大约 10-20 倍。

很多时候我发现，自然编码的 Haskell 解决方案比 C 慢大约 10 倍。我预计 GHC 是一个非常巧妙地优化的编译器和任务，这样看起来并不那么困难。

因此，人们会期望它比 C 慢 1.5-2 倍。问题出在哪里？

这个问题可以更好地解决吗？

这是我与之比较的 C 代码：

long long sum = 0;
int n = 0, i = 1;

for (;;) {

  if (i % 2 == 0) {
    sum += i;
    n++;
  }

  if (n == 15000000)
    break;

  i++;
}

Edit 1：我真的知道，它可以在 O(1) 内计算。请抵抗。

Edit 2: 我真的知道，即使是[2,4..]但功能even可能是别的东西O(1)并且需要作为函数来实现。

列表不是循环

因此，如果使用列表作为循环替换，请不要感到惊讶，如果循环体很小，您会得到更慢的代码。

nats = [1..] :: [Int]
evens = filter even nats :: [Int]

dumbSum :: Int
dumbSum = sum $ take 15000000 evens

sum不是一个“好消费者”，因此 GHC 还不能完全消除中间列表。

如果您使用优化进行编译（并且不导出nat），GHC 足够聪明，可以融合filter通过枚举，

Rec {
Main.main_go [Occ=LoopBreaker]
  :: GHC.Prim.Int# -> GHC.Prim.Int# -> [GHC.Types.Int]
[GblId, Arity=1, Caf=NoCafRefs, Str=DmdType L]
Main.main_go =
  \ (x_aV2 :: GHC.Prim.Int#) ->
    let {
      r_au7 :: GHC.Prim.Int# -> [GHC.Types.Int]
      [LclId, Str=DmdType]
      r_au7 =
        case x_aV2 of wild_Xl {
          __DEFAULT -> Main.main_go (GHC.Prim.+# wild_Xl 1);
          9223372036854775807 -> n_r1RR
        } } in
    case GHC.Prim.remInt# x_aV2 2 of _ {
      __DEFAULT -> r_au7;
      0 ->
        let {
          wild_atm :: GHC.Types.Int
          [LclId, Str=DmdType m]
          wild_atm = GHC.Types.I# x_aV2 } in
        let {
          lvl_s1Rp :: [GHC.Types.Int]
          [LclId]
          lvl_s1Rp =
            GHC.Types.:
              @ GHC.Types.Int wild_atm (GHC.Types.[] @ GHC.Types.Int) } in
        \ (m_aUL :: GHC.Prim.Int#) ->
          case GHC.Prim.<=# m_aUL 1 of _ {
            GHC.Types.False ->
              GHC.Types.: @ GHC.Types.Int wild_atm (r_au7 (GHC.Prim.-# m_aUL 1));
            GHC.Types.True -> lvl_s1Rp
          }
    }
end Rec }

但这就是 GHC 融合所能达到的程度。你只剩下拳击了Ints 并构建列表单元格。如果你给它一个循环，就像你给 C 编译器一样，

module Main where

import Data.Bits

main :: IO ()
main = print dumbSum

dumbSum :: Int
dumbSum = go 0 0 1
  where
    go :: Int -> Int -> Int -> Int
    go sm ct n
        | ct >= 15000000 = sm
        | n .&. 1 == 0   = go (sm + n) (ct+1) (n+1)
        | otherwise      = go sm ct (n+1)

你会得到你期望的 C 版本和 Haskell 版本之间运行时间的近似关系。

这种算法并不是 GHC 所教的能够很好优化的，在将有限的人力投入这些优化之前，还有更大的鱼要炸。