4
\$\begingroup\$

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 :)
\$\endgroup\$
2
\$\begingroup\$
  • 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
\$\endgroup\$
  • \$\begingroup\$ Thanks for the elaborate review! I don't really understand why seq is used there, though. I know what it does, but I don't see the point of using it there. Can you explain? \$\endgroup\$ – Tim Vermeulen Feb 11 '17 at 21:40
  • \$\begingroup\$ @TimVermeulen it was part of the patch, although it was missing in the proposal. The rational is missing, but since we need to evaluate f x either way, there is no harm in adding seq at this point. On the contrary: we have to save one thunk less (per element). It's often a good idea to have something in WHNF (or even NF) if you know that you're going to use it. \$\endgroup\$ – Zeta Feb 11 '17 at 22:26
  • \$\begingroup\$ Alright, that's something to think about. :) \$\endgroup\$ – Tim Vermeulen Feb 11 '17 at 22:33
2
\$\begingroup\$

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 _ _ = []
\$\endgroup\$
  • \$\begingroup\$ Your solution computes x + y twice for each (x, y) pair, right? Also, I can't seem to import minimumOn - do I need to install it somehow? \$\endgroup\$ – Tim Vermeulen Feb 11 '17 at 17:06
  • 1
    \$\begingroup\$ @TimVermeulen: It doesn't exist. It was proposed, but not included. Maybe Gurkenglas uses a custom Prelude that contains minimumOn. But it's not in the GHC source. Also, yes. x + y gets computed twice. \$\endgroup\$ – Zeta Feb 11 '17 at 19:08

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.