[NumericPrelude] 'sum' optimized for particular types

[Henning Thielemann]

Hi all,

in general summing from the end of the list to the beginning is the way 
that works for all types:

   sum = foldr (+) zero

However it is inefficient for most types (Integer, Rational, Double, 
vectors, Polynomial) and only efficient for Peano numbers and
Number.NonNegativeChunky.

A universal efficient method 'sum' would allow us to implement:

   length :: Ring.C n => [a] -> n
   length = sum . map (const one)

Writing an optimizer rule that replaces foldr-based sum by foldl-based sum 
for particular types would not be good, because this optimization will 
likely reduce linear memory consumption to constant memory consumption, 
and such optimizations are too much of a surprise, or to put it 
differently, it is not safe to rely on them. It is also not clear whether 
this would automatically scale to complex types. A user would have to 
write a RULE for every new atomic type in the Additive class. Interpreters 
like Hugs or GHCi cannot make use of such optimizer rules.

Another solution would be to turn 'sum' from a function to a method of 
Additive, where the default implementation is

   sum = foldl (+) zero

However, how would I implement the Additive instance for pairs (as example 
for vectors, polynomials and so on) ?

   instance (Additive.C a, Additive.C b) => Additive C (a,b) where
     sum = mapPair (sum, sum) . unzip

This way I could make use of the optimal summation order for the pair 
element types. I can even handle the case (a = Integer) and (b = Peano). 
However I risk a space leak, because both sums are computed independently. 
That is, between evaluation of the first and the second sum, the complete 
input list must be hold in memory.

A way to handle both left- and right-biased summation could be to 
associate types like Integer with an Endo monoid and types like Peano with 
a Sum monoid and combine the monoid values always in a right-biased 
manner.

for Integer:
    sumMonoid x = Endo (x+)
    sumRun (Endo f) = f zero

for Peano
    sumMonoid x = Sum x
    sumRun (Sum x) = x

   sum = sumRun . foldr (Monoid.<*>) Monoid.idt . map sumMonoid

However the association of Integer with Endo and Peano with Sum would need 
functional dependencies or associated types, both of them are absent from 
NumericPrelude so far and they would turn the current Haskell98 class 
Additive into something considerably more complicated. I am uncertain, 
what to do.