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)
``````