Daniel Fischer
Am Mittwoch 10 März 2010 22:33:43 schrieb TeXitoi:
After programming as an exercice the sum function, my version is faster than the Data.List's version. Looking at the source code, Data.List uses a foldl and not a foldl'. foldl' seems faster and allows to use very big lists. So, why is foldl used by Data.List for sum?
Because Haskell is a non-strict language, and foldl' is strict -- someone might write a (legitimate) Num instance for a datatype such that
foldl (+) 0 xs
returns a good value, but
foldl' (+) 0 xs
gives
***Exception: Prelude.undefined
for some lists xs. Since Haskell is non-strict, sum xs should give a good value then.
Yeah, I see. I've thought at that looking the comment of maximum.
However, with optimisations turned on, for the standard Num instances, GHC knows that sum is actually strict and produces code as if sum were defined using foldl'.
OK, good to know.
Depending on how you timed the functions, there are several ways how you could have obtained your result without there being an actual difference between your implementation and the library's for Int, Integer, ...
In ghci, that's explain the non optimized version. Same result without any option to ghc. I have similar performances between sum and foldl' (+) 0 with ghc -O2. Thanks for the explainations. -- Guillaume Pinot http://www.irccyn.ec-nantes.fr/~pinot/ « Les grandes personnes ne comprennent jamais rien toutes seules, et c'est fatigant, pour les enfants, de toujours leur donner des explications... » -- Antoine de Saint-Exupéry, Le Petit Prince () ASCII ribbon campaign -- Against HTML e-mail /\ http://www.asciiribbon.org -- Against proprietary attachments