Warum ist die Summe langsamer als faltl 'in Haskell?

Question

Wie ist die Standardeinstellung sum in Ghc ~ 10 mal langsamer als die foldl' (stricter equivalentfoldl) entspricht? Und wenn das der Fall ist, warum wird es nicht mit foldl' implementiert?

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) 

Zur Vollständigkeit sind hier auch die Statistiken von foldl und 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) 

Sieht aus wie sum realisiert wird foldl seit ihrer Laufzeit ähnlich ist. Getestet auf ghc 7.10.2.

Answer 1

Die sum Funktion wird mit foldl in GHC implementiert:

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

wie in the source zu sehen.

Es muss so sein, denn es ist die Spezifikation in the Haskell report.

Die Begründung war wahrscheinlich, dass für bestimmte träge Elementtypen der Liste foldl das Richtige zu tun ist. (Ich persönlich denke, dass foldl ist fast immer falsch und nur foldl' sollte verwendet werden.)

Mit ausreichender Optimierung wird GHC inline diese Definition, spezialisiert es auf die Elementart zur Hand, beachten Sie, dass die Schleife ist streng und zwingen die Auswertung des Akkumulators in jeder Iteration; effektiv dies in eine foldl', wie von @ AndrásKovács beobachtet.

Da GHC-7.10, sum itself eine Methode der Foldable-Klasse ist, und die Standarddefinition geht über foldMap. Die instance Foldable [] überschreibt dies jedoch mit der obigen Definition von sum.

Answer 2

Um @Joachim Breitners Antwort zu ergänzen, fand ich diese blog post, eine sehr interessante Lektüre (aus der Reddit-Diskussion, dank @ZhekaKozlov für den Link).

Als Haskell 1.0 an diesem Tag vor 24 Jahren veröffentlicht wurde, gab es keine Seq-Funktion, also gab es keine andere Wahl, als foldl auf die "klassische" Art zu definieren.

Schließlich, sechs Jahre später nach viel Diskussion, haben wir die Seq-Funktion in Haskell 1.3. Obwohl tatsächlich in Haskell 1.3 Seq Teil einer Eval-Klasse war, konnte man sie nicht überall verwenden, wie zum Beispiel in foldl.

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

Haskell 1.4 und Haskell 98 wurde für folgenden die Eval Klasse Einschränkung befreien aber foldl wurde nicht geändert: In Haskell 1.3 Sie mit der Art wären zu definieren foldl‘haben. Hugs und GHC und andere Implementierungen fügten das nicht standardisierte Faltblatt hinzu.

Ich vermute, dass die Leute es dann als ein Problem der Kompatibilität und Trägheit betrachteten. Es war einfach genug, ein nicht standardmäßiges Faltblatt hinzuzufügen, aber Sie können den Standard nicht so einfach ändern.

Ich vermute, wenn wir von Anfang an seq gehabt hätten, hätten wir foldl damit definiert.

Miranda, eine der Vorgängersprachen von Haskell, hatte bereits 5 Jahre vor Haskell 1.0.

BTW, ich habe es geschafft, 20 ms mehr von

So

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

mit sich rasieren, ich denke, foldl1' die Standardeinstellung für sum und product (mit besonderer Umgang mit leeren Listen) sein sollte.