[Haskell] specification of sum

Lennart Augustsson lennart at augustsson.net
Tue Nov 1 19:19:42 EST 2005


Cale Gibbard wrote:
> On 01/11/05, Sebastian Sylvan <sebastian.sylvan at gmail.com> wrote:
> 
>>On 11/1/05, Scherrer, Chad <Chad.Scherrer at pnl.gov> wrote:
>>
>>>I was wondering... In my experience, it's worked much better to use
>>>
>>>sum' = foldl' (+) 0
>>>
>>>than the built-in "sum" function, which leaks memory like crazy for
>>>large input lists. I'm guessing the built-in definition is
>>>
>>>sum = foldr (+) 0
>>>
>>>But as far as I know, (+) is always strict, so foldl' seems much more
>>>natural to me. Is there a case where the build-in definition is
>>>preferable?
>>
>>The library definition in ghc actually uses foldl.
>>It's conceivable that you may not want (+) to be non-strict for
>>certain data types.
>>The question then becomes, is there a case where you want _sum_ to be
>>non-strict?
>>
> 
> 
> I'd argue that the likely answer is no, given that (+) is an operation
> in an Abelian group and not a monoid. Regardless of whether (+) is
> strict, when you compute a sum you will always have to consume the
> entire list.

(+) is not an operation in an Abelian group.  (+) is a function with
type a->a->a for some particular a. Haskell makes no mention about (+)
having any other properties.

Furthermore, ghc has a WRONG definition of sum.  You cannot change a
foldr into a foldl, unless the operator is associative, and (+) does
not have to be.

	-- Lennart

PS.  I think additional properties of class methods would be great,
but since Haskell cannot enforce them we should not rely on them.


More information about the Haskell mailing list