Mark Needham

Thoughts on Software Development

Haskell: Maximum Int value

without comments

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)
Be Sociable, Share!

Written by Mark Needham

May 7th, 2012 at 9:18 am

Posted in Haskell

Tagged with