### Re: specification of sum

Cale Gibbard <cgibbard <at> gmail.com>

2005-11-01 23:38:01 GMT

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. This is because until you have observed the last element
of the list, nothing can be said about the final result. To see this,
it's enough to see that even if the sum of all the other elements of
the list is g, the final element could be -g + h, which would give a
final result of h, regardless of what g is.

(Continue reading)