[NumericPrelude] 'sum' optimized for particular types
Henning Thielemann
lemming at henning-thielemann.de
Fri Jul 16 05:03:14 EDT 2010
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.
More information about the Numeric-Prelude
mailing list