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?

Some imports:

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.

### Like this:

Like Loading...

*Related*

Tags: bonsai, code, difference, Haskell, kata, maximum, praxis, programming

This entry was posted on April 1, 2011 at 1:33 pm and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply