Haskell: Maximum Int value
One of the algorithms covered in Algo Class was the closest pairs algorithm – an algorithm used to determine which pair of points on a plane are closest to each other based on their Euclidean distance.
My real interest lies in writing the divide and conquer version of the algorithm but I started with the brute force version so that I’d be able to compare my answers.
This is the algorithm:
minDist = infinity
for each p in P:
for each q in P:
if p ≠ q and dist(p, q) < minDist:
minDist = dist(p, q)
closestPair = (p, q)
return closestPair‘infinity’ in this case could be the maximum value that an Int could hold which on a 64 bit architecture would be 263 so I hardcoded that into my implementation:
o
bfClosest :: (Ord a, Floating a) => [(a, a)] -> Maybe ((a, a), (a, a)) bfClosest pairs = snd $ foldl (\ acc@(min, soFar) (p1, p2) -> if distance p1 p2 < min then (distance p1 p2, Just(p1, p2)) else acc) (2^63, Nothing) [(pairs !! i, pairs !! j) | i <- [0..length pairs - 1], j <- [0..length pairs-1 ], i /= j] where distance (x1, y1) (x2, y2) = sqrt $ ((x1 - x2) ^ 2) + ((y1 - y2) ^ 2)
We’re comparing each point with all the others in the list by folding over a collection of all the combinations and then passing the pair with the smallest distance between points as part of our accumulator.
More by chance than anything else I was reading the Learn You a Haskell chapter on types and type classes and came across the maxBound function which does exactly what I want:
> 2 ^ 63 9223372036854775808 > maxBound :: Int 9223372036854775807
We can’t plug that straight into the function as is because the fold inside ‘bfClosest’ expects a float and had been automatically coercing 263 into the appropriate type.
We therefore use ‘fromIntegral’ to help us out:
bfClosest :: (Ord a, Floating a) => [(a, a)] -> Maybe ((a, a), (a, a)) bfClosest pairs = snd $ foldl (\ acc@(min, soFar) (p1, p2) -> if distance p1 p2 < min then (distance p1 p2, Just(p1, p2)) else acc) (fromIntegral (maxBound :: Int), Nothing) [(pairs !! i, pairs !! j) | i <- [0..length pairs - 1], j <- [0..length pairs-1 ], i /= j] where distance (x1, y1) (x2, y2) = sqrt $ ((x1 - x2) ^ 2) + ((y1 - y2) ^ 2)
