Here's my second try at pairwise summation in Haskell:

pairwiseSum :: (Num a) => [a] -> a
pairwiseSum [] = 0
pairwiseSum [x] = x
pairwiseSum x = pairwiseSum (sumPairs x)

sumPairs :: (Num a) => [a] -> [a]
sumPairs [] = []
sumPairs [x] = [x]
sumPairs (x:y:xs) = ((x + y) : sumPairs xs)

I ran both versions on pairwiseSum (map exp [1,0.9999..(-56.0)]), and this one's noticeably faster. Is it well written?

ETA: here are some runs comparing pairwiseSum with sum :

*Main> pairwiseSum (map exp [1,0.9999..(-56.0)])
*Main> sum (map exp [1,0.9999..(-56.0)])
*Main> pairwiseSum (map exp [1,0.99999..(-56.0)])
*Main> sum (map exp [1,0.99999..(-56.0)])

The previous version of pairwiseSum gave 27184.177448160022 as the sum of the first list. On the second, I counted to 13 while pairwiseSum ran and to 11 while sum ran.

  • \$\begingroup\$ type :set +s at GHCi and you get runtime stats with time and memory usage. But: GHCi is not the right way to test timing, take a look at criterion: hackage.haskell.org/package/criterion \$\endgroup\$ – Franky Apr 15 at 7:08

Linking the other version of pairwiseSum here Pairwise summation in Haskell

That version is an O(nlogn) algorithm, while this one is linear [ie O(n)]. In fact this version is probably the best you can do in Haskell with lists. It's reminiscient of a fold, which is the natural operation on a list data structure.

The previous version has a bunch of wasted effort as the lists are recursively split. Each time it's split the algorithm has to traverse the whole array. So it's perfectly reasonable that the first version is slower


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.