Pairwise summation in Haskell

Question

I'm new to Haskell, and I figured that pairwise summation is something I could do easily. I wrote this:

pairwiseSum :: (Num a) => [a] -> a
pairwiseSum [] = 0
pairwiseSum [x] = x
pairwiseSum (x:xs) = (pairwiseSum (everyOther (x:xs))) + (pairwiseSum (everyOther xs))

everyOther :: [a] -> [a]
everyOther [] = []
everyOther [x] = [x]
everyOther (x:_:xs) = x : everyOther xs

Given [0,1,2,3,4,5,6,7], this computes (((0+4)+(2+6))+((1+5)+(3+7))), whereas my C(++) code computes (((0+1)+(2+3))+((4+5)+(6+7))). How does this affect optimization?

How easy is it to read? Could it be written better?

How can I test it? I have three tests in C++:

• add the odd numbers [1,3..(2*n-1) and check that the sum is n²;
• add 100000 copies of 1, 100000 copies of 0.001, ... 100000 copies of 10^-18 and check for the correct sum;
• add 0x36000 terms of a geometric progression with ratio exp(1/4096).

To test execution time, I use 1000000 copies and 16 times as many terms of exp(1/65536).

Answer 1

Your code doesn’t have great complexity. I think it’s \$\mathcal{O}(2^n)\$, but I’m rusty so maybe somebody can come in with an assist. The thing to remember is that Haskell lists are linked lists and laziness doesn’t get you out of paying the cost of walking them. Each call to everyOther is \$\mathcal{O}(n)\$, and you pay that twice with every recursive call.

There are a bunch of ways we could solve this. If you actually want to process lists like a binary tree for some reason, then I’d recommend just turning the list into a binary tree and processing that if you’re favoring clarity. If you do that you could get the compiler to fuse away the intermediate structure, but it might not happen automatically without some pragmas.

You could also decompose your problem into smaller, easier to solve bits, then reassemble them into your ultimate solution.

-- Do a single pass through a list, summing elements pairwise
sumPairs :: Num a => [a] -> [a]
sumPairs [] = [0]
sumPairs [n] = [n]
sumPairs (m:n:xs) = m + n : sumPairs xs

-- Identify when there's only a single element left in the list
isLengthOne :: [a] -> Bool
isLengthOne [_] = True
isLengthOne _ = False

-- Repeatedly apply sumPairs until you find a one element list and return that value
pairwiseSum :: Num a => [a] -> a
pairwiseSum = head . find isLengthOne . iterate sumPairs

If you’re looking for testing and benchmarking libraries, check out QuickCheck for testing and criterion for benchmarking.

QuickCheck does what’s known as property testing, instead of constructing elaborate unit tests the library helps you to test random inputs to see if some property holds. Usually that’s things like testing that a function to insert an element into a collection increases that collections size by one, or that after a random sequence of inserts the collection contains all of the elements that were inserted. In this case you can use it to prove equivalence between two versions of functions that should have identical results. I.e.—

import Test.QuickCheck

prop_sumsEqual :: [Int] -> Bool
prop_sumsEqual xs = pairwiseSum xs == sum xs

main :: IO ()
main = quickCheck prop_sumsEqual

criterion handles re-running benchmarks for you and gives you all sorts of fancy statistical output. You might use it like—

import Criterion.Main

main :: IO ()
main = defaultMain [bench "pairwiseSum" $ nf pairwiseSum [1 .. 10000]]

You could bench sum by adding another list element there and compare the difference. Or you could take advantage of your benchmarks being values to generate a series, that might help you understand how your execution time grows with input size.

mkBench_pairwiseSum :: Int -> Benchmark
mkBench_pairwiseSum n = bench ("pairwiseSum:" ++ show n) $ nf pairwiseSum [1 .. n]

main :: IO ()
main = defaultMain $ map mkBench_pairwiseSum [10000, 20000 .. 100000]