In today’s Programming Praxis exercise, our goal is to find the maximum difference between two numbers in a list, with the condition that the higher number comes last. We need to write both a quadratic and a linear algorithm. Let’s get started, shall we?
import Data.List import qualified Data.List.Key as K import Data.Tuple.HT import Test.QuickCheck
The quadratic number is a matter of finding the highest subsequent number for each number in the list and returning the pair with the greatest difference. The two reverse functions are needed since K.maximum unfortunately chooses the latter of the two elements when the comparison yields the same value.
maxDiffNaive :: (Enum a, Ord a, Num a) => [a] -> (a, a, a) maxDiffNaive = K.maximum thd3 . reverse . map f . init . tails . zip [0..] where f xs = (i,j,hi-lo) where (i,lo) = head xs (j,hi) = K.maximum (subtract lo . snd) (reverse xs)
The linear version can be represented with a simple fold. The accumulator holds the current minimum value as well as the current maximum difference.
maxDiffSmart :: (Ord a, Num a, Enum a) => [a] -> (a, a, a) maxDiffSmart = snd . (\(x:xs) -> foldl f (x,(0,0,0)) xs) . zip [0..] where f ((i',lo), (i,j,d)) (j',x) = (if x < lo then (j',x) else (i',lo), if x-lo > d then (i',j',x-lo) else (i,j,d))
Testing whether the two functions produce the same output can be easily automated using QuickCheck.
prop_maxDiff :: [Integer] -> Property prop_maxDiff x = not (null x) ==> (maxDiffNaive x == maxDiffSmart x)
To test everything we use a combination of unit tests and QuickCheck.
main :: IO () main = do let test f = do print $ f [4,3,9,1,8,2,6,7,5] == (3,4,7) print $ f [4,2,9,1,8,2,6,7,5] == (1,2,7) print $ f [4,3,9,1,2,6,7,8,5] == (3,7,7) print $ f [5,4,3] == (0,0,0) print $ f [1,3,3] == (0,1,2) test maxDiffNaive test maxDiffSmart quickCheck prop_maxDiff
Everything seems to be working correctly.