Smallest Difference



In [1]:

    
import Data.List



In [2]:

    
considerPairs :: Ord a => [a] -> [a] -> [(a, a)]

considerPairs _ [] = []
considerPairs [] _ = []
considerPairs (x:xs) (y:ys) = (x, y) : if x < y then considerPairs xs (y:ys)
                                                else considerPairs (x:xs) ys
                      
candidatePairs xs ys = considerPairs (sort xs) (sort ys)



In [3]:

    
smallestDifference :: (Num a, Ord a) => [a] -> [a] -> (a, (a, a))
smallestDifference xs ys =
    minimum $ map (\pair -> (abs $ uncurry (-) pair, pair)) (candidatePairs xs ys)



In [4]:

    
smallestDifference [1, 3, 15, 11, 2] [23, 127, 235, 19, 8]









    





(3,(11,8))

Or else, if we want to restrict possible inputs to natural numbers...



In [5]:

    
import Numeric.Natural



In [6]:

    
smallestDifference' :: [Natural] -> [Natural] -> (Natural, (Natural, Natural))
smallestDifference' xs ys =
    minimum $ map (\pair -> (distanceMetric pair, pair)) (candidatePairs xs ys)
    where distanceMetric (x, y) = if x > y then x - y else distanceMetric (y, x)

Note that we define our own distanceMetric above instead of using abs (x - y), because x - y may produce a non-natural number (and thus throw an exception) unless it is known that x >= y.



In [7]:

    
smallestDifference' [1, 3, 15, 11, 2] [23, 127, 235, 19, 8]









    





(3,(11,8))