1
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I must be missing something, but this appears to compute the sum of the input list. If you wanted to make a list of the pairwise sums you could do something like pairwiseSums xs = zipWith (+) (everyOther xs) (everyOther $ drop 1 xs). If your goal was to make a sum function, then I must admit they way you’ve written it is somewhat confusing. \$\endgroup\$ – cole Apr 9 at 23:31
  • \$\begingroup\$ It does indeed compute the sum of the input list. The purpose of doing it pairwise is to reduce the total roundoff error when summing long lists of floating-point numbers. \$\endgroup\$ – Pierre Abbat Apr 11 at 8:40
0
\$\begingroup\$

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]
\$\endgroup\$
4
  • 1
    \$\begingroup\$ The complexity shouldn’t be as bad as O(2^n) because the list’s elements are the leaves of the tree. If we paired each node with its neighbor recursively, we’d halve the nodes each time, giving a depth of log(n). Suppose in a worst case that the function is eagerly evaluated. Then at the root we do O(n) work to split up the list. For its children, we do O(n/2) work, but since there are two children that comes out to be O(n). In general, at each depth from i=log n to 0 there are n/2^i children, but the work done is 2^i. So in total that’s n*log n. However with laziness it might be linear. \$\endgroup\$ – cole Apr 10 at 22:30
  • \$\begingroup\$ Mm yeah logs, that’s right. I’m not sure where you see a laziness opportunity though, the zebra striping seems likely to completely defeat the compiler. But I’ve been wrong before and I’ll be wrong again. \$\endgroup\$ – bisserlis Apr 10 at 23:09
  • 1
    \$\begingroup\$ I wasn’t sure about how laziness factored in, so you’re probably right about it not being linear. I wanted to acknowledge that I wasn’t accounting for it. \$\endgroup\$ – cole Apr 11 at 3:40
  • \$\begingroup\$ It's O(n*log n), maybe O(n), but I'm concerned about the proportionality constant: how fast is the Haskell code compared to C code that is optimized for cache and is given an array that's in a block of memory. But the space complexity is O(n), since it spreads out the entire list before starting to sum it. It should be O(log n). I'll be back with an improved version. \$\endgroup\$ – Pierre Abbat Apr 11 at 9:00

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.