なぜhaskellのfoldlより和が遅いのですか？

Question

ghcのデフォルトsumは、foldl'（stricter equivalentはfoldl）よりも10倍遅いですか？その場合、なぜfoldl'を使用して実装されていないのですか？完全のために

import Data.List 
> foldl' (+) 0 [1..10^7] 
50000005000000 
(0.39 secs, 963,528,816 bytes) 

> sum [1..10^7] 
50000005000000 
(4.13 secs, 1,695,569,176 bytes) 

ここもfoldlとfoldrの統計情報です。

> foldl (+) 0 [1..10^7] 
50000005000000 
(4.02 secs, 1,695,828,752 bytes) 

> foldr (+) 0 [1..10^7] 
50000005000000 
(3.78 secs, 1,698,386,648 bytes) 

彼らのランタイムが似ているので、sumがfoldlを使用して実装されているように見えます。 ghc 7.10.2でテストされています。 in the sourceを見ることができるように

-- | The 'sum' function computes the sum of a finite list of numbers. 
sum      :: (Num a) => [a] -> a 
{-# INLINE sum #-} 
sum      = foldl (+) 0 

：

Answer 1

sum機能はGHCでfoldlを用いて実現されます。

仕様はin the Haskell reportなので、このようにする必要があります。

リストの特定の遅延要素タイプの場合、foldlが正しいことが考えられます。 （私は個人的にfoldlはほとんど常に間違っているとだけfoldl'を使用する必要があると思います。）

十分な最適化では、GHCは、その定義をインライン手元にある要素の型に特化し、ループが厳格であることがわかり、そして力になります各反復におけるアキュムレータの評価。効果的にこれをfoldl'に変えました。@AndrásKovácsが観察しました。

GHC-7.10の場合、sum itselfはFoldableタイプクラスのメソッドであり、デフォルト定義はfoldMapです。しかしながら、instance Foldable []は、上記の定義をsumに置き換えます。

Answer 2

@Joachim Breitnerの答えを補足するために、私はこのblog postという非常に興味深い読者を見つけました（リンクについては@ZhekaKozlovのおかげでレッドディシジョンの議論から得ました）。

24日前にHaskell 1.0が公開されたとき、seq関数はまったくなかったので、foldlを「古典的」な方法で定義する以外に選択肢はありませんでした。

最終的に、議論の6年後、私たちはHaskell 1.3でseq関数を得ました。実際にHaskell 1.3ではseqはEvalクラスの一部でしたので、foldlなどのどこでも使用することはできませんでした。 Haskellの1.3では、あなたがタイプとfoldlの「を定義しなければならなかったでしょう：

foldl' :: Eval b => (b -> a -> b) -> b -> [a] -> b 

ハスケル1.4とはHaskell 98は、配列のための評価クラスの制約を処分したが、foldlのは変更されませんでした。 HugsやGHCなどの実装では、非標準のfoldl 'が追加されました。

私は人々がそれを互換性と慣性の問題と考えていたと考えています。非標準のfoldl 'を追加するだけでも簡単でしたが、標準を簡単に変更することはできません。

最初からseqがあった場合は、それを使ってfoldlを定義していたと思います。

Haskellの先行言語の1つであるMirandaは、すでにHaskell 1.0の5年前にseqを持っていました。

ところで、私はそう

foldl1' (+) [1..10^7] 

を使用して20ミリ以上剃ることができた、私はfoldl1'は（空のリストの特別な処理と）sumとproductのデフォルトであるべきと思います。