Pairwise summation in Haskell, take two Here's my second try at pairwise summation in Haskell:
pairwiseSum :: (Num a) =&gt; [a] -&gt; a
pairwiseSum [] = 0
pairwiseSum [x] = x
pairwiseSum x = pairwiseSum (sumPairs x)

sumPairs :: (Num a) =&gt; [a] -&gt; [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&gt; pairwiseSum (map exp [1,0.9999..(-56.0)])
27184.177448160026
*Main&gt; sum (map exp [1,0.9999..(-56.0)])
27184.177448147617
*Main&gt; pairwiseSum (map exp [1,0.99999..(-56.0)])
271829.5419903211
*Main&gt; sum (map exp [1,0.99999..(-56.0)])
271829.54198831413

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.
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