为什么对本地列表求和比用“GHC -O2”对教会编码列表求和慢？

为了测试教会编码的列表如何针对用户定义的列表和本机列表执行，我准备了 3 个基准测试：

用户定义的列表

data List a = Cons a (List a) | Nil deriving Show
lenumTil n        = go n Nil where
    go 0 result   = result
    go n result   = go (n-1) (Cons (n-1) result)
lsum Nil          = 0
lsum (Cons h t)   = h + (lsum t)

main = print (lsum (lenumTil (100000000 :: Int)))

本地列表

main = print $ sum ([0..100000000-1] :: [Int])

教会名单

fsum   = (\ a -> (a (+) 0))
fenumTil n cons nil = go n nil where
    go 0 result    = result
    go n result    = go (n-1) (cons (n-1) result)
main = print $ (fsum (fenumTil (100000000 :: Int)) :: Int)

基准测试结果出乎意料：

用户定义的列表

-- 4999999950000000
-- real 0m22.520s
-- user 0m59.815s
-- sys  0m20.327s

本地列表

-- 4999999950000000
-- real 0m0.999s
-- user 0m1.357s
-- sys  0m0.252s

教会名单

-- 4999999950000000
-- real 0m0.010s
-- user 0m0.002s
-- sys  0m0.003s

人们会期望，通过针对本机列表的大量特定优化，它们将表现最佳。然而，教会列表的表现比它们高出 100 倍，比用户定义的 ADT 高出 2250 倍。我已经编译了所有程序GHC -O2。我尝试过更换sum by foldl'，结果相同。我尝试添加用户输入以确保教堂列表版本没有优化为常量。arkeet在 #haskell 上指出，通过检查 Core，原生版本有一个中间列表，但为什么呢？强制分配额外的reverse，所有 3 个的性能大致相同。

GHC 7.10 有调用数量 http://www.joachim-breitner.de/publications/CallArity-TFP.pdf分析，让我们定义foldl按照foldr从而让左边的折叠，包括sum，参与融合。 GHC 7.8 还定义了sum with foldl但它无法将列表融合掉。因此，GHC 7.10 的性能最佳且与 Church 版本相同。

Church 版本在任一 GHC 版本中进行优化都是轻而易举的事情。我们只需要内联(+) and 0 into fenumTil，然后我们就有了一个明显的尾递归go它可以很容易地拆箱，然后由代码生成器转换为循环。

用户定义的版本不是尾递归的，它在线性空间中工作，这当然会破坏性能。