Find two numbers in a sorted array whose sum is closest to a given number

Question

Given a sorted array and a number x, find a pair in array whose sum is closest to x.

Here's my solution:

import Data.List (minimumBy)
import Data.Ord (comparing)

closestPairSum :: (Num a, Ord a) => [a] -> a -> (a, a)
closestPairSum xs n = snd $ minimumBy (comparing fst) pairs
  where 
    pairs = sums xs (reverse xs)
    sums xxs@(x:xs) yys@(y:ys) = let sum = x + y in
      if n < sum
      then (sum - n, (x, y)) : sums xxs ys
      else (n - sum, (x, y)) : sums xs yys
    sums _ _ = []

I'm mostly self-taught, so I would love to know in which ways my code is not according to common practice. More specifically:

• How can I more clearly align my let-in and if-then-else expressions?
• I use an intermediate list of (a, (a, a)) tuples, which I'm not thrilled about. Is there a more elegant way to do this, without sacrificing performance?
• I'm on the fence about sum xs (reverse xs) vs sum xs $ reverse xs. Is this just considered nitpicking, or do people have a strong opinion about this?
• Would it make more sense to swap the parameters of this function? I have the feeling that a would usually precede [a] with pointfree style in mind, but I'm not sure about this one.
• Anything else that I might not have thought of :)

Answer 1

• How can I more clearly align my let-in and if-then-else expressions?

Well, that's up to you, to be honest. You could put let ... in into a new line, for example:

sums xxs@(x:xs) yys@(y:ys) = 
  let sum = x + y 
  in if n < sum
     then (sum - n, (x, y)) : sums xxs ys
     else (n - sum, (x, y)) : sums xs yys
sums _ _ = []

I usually prefer guards:

sums xxs@(x:xs) yys@(y:ys) = 
  | n < sum   = (sum - n, (x, y)) : sums xxs ys
  | otherwise = (n - sum, (x, y)) : sums xs yys
  where sum = x + y 
sums _ _ = []

I said "usually", because I don't like the dangling sums at the end.

• I use an intermediate list of (a, (a, a)) tuples, which I'm not thrilled about. Is there a more elegant way to do this, without sacrificing performance?

It's fine. sortOn from Data.List basically uses the same approach:

sortOn f = map snd . sortBy (comparing fst) . map (\x -> let y = f x in y `seq` (y, x))

If something is fine enough for the standard library, it should be fine enough for you. Note that the seq might be necessary to yield more performance.

• I'm on the fence about sum xs (reverse xs) vs sum xs $ reverse xs. Is this just considered nitpicking, or do people have a strong opinion about this?

That's nitpicking. Some people prefer ($), since you cannot accidentally forget a ), others prefer parentheses, since they are easier to understand for beginners. The generated program will behave the same.

• Would it make more sense to swap the parameters of this function? I have the feeling that a would usually precede [a] with pointfree style in mind, but I'm not sure about this one.

If this function will be part of a collection, then it's more important that all your functions follow the same style. Other than that, it's preferred that you use the argument which will change seldom first, or, if it's using a container, the container last. So yes, your function would be a perfect candidate for switching.

• Anything else that I might not have thought of :)

Yes. Don't use reserved names, if possible. sum is defined in the Prelude, you've used it to bind x + y. Also don't use the same names twice. You've used xs both in your closestPairSum as well as in sums. This can lead to errors when you refactor your function.

Other than that: Well done. For comparison, here is how I would write your function:

import Data.List (minimumBy)
import Data.Ord (comparing)

closestPairSum :: (Num a, Ord a) => a -> [a] -> (a, a)
closestPairSum n = snd . minimumBy (comparing fst) . pairs
  where 
    pairs xs = sums xs (reverse xs)

    sums [] _ = []
    sums _ [] = []
    sums xxs@(x:xs) yys@(y:ys)
      | n < s     = (s - n, (x, y)) : sums xxs ys -- sum greater than n, use lesser y
      | otherwise = (n - s, (x, y)) : sums xs yys -- sum lesser than n, use greater x
      where
        s = x + y

Answer 2

The "intermediate array" takes no extra space due to lazy evaluation. minimumBy . comparing is minimumOn. Yes, swapping the parameters makes sense. Inline then and else once more. I wouldn't worry so much about constant factors - have you compiled it with -O2 and tested (eg with criterion)?

import Data.List (minimumOn)

closestPairSum :: (Num a, Ord a) => a -> [a] -> (a, a)
closestPairSum n xs = minimumOn (abs . (n-) . uncurry (+)) pairs where
  pairs = sums xs (reverse xs)
  sums xxs@(x:xs) yys@(y:ys) = (x, y) : if n < x + y
    then sums xxs ys
    else sums xs yys
  sums _ _ = []