Determining closest pair of points using distance function, Haskell

Question

Im trying to figure out how get the closest pair of points with this function for a project. I'm getting an error I don't quite understand. Thanks for the help. I have given the distance formula which works, I'm unsure if I am calling the distance function properly in the closestPairs function.

type Point a = (a,a)

-- Determine the true distance between two points.
distance :: (Real a, Floating b) => Point a -> Point a -> b
distance (x1,y1) (x2,y2) = sqrt (realToFrac ((x1 - x2)^2 + (y1 - y2)^2))

type Pair a = (Point a, Point a)

-- Determine which of two pairs of points is the closer.
closerPair :: Real a => Pair a -> Pair a -> Pair a
closerPair (p1,p2) (q1,q2) | distance (p1, p2) > distance (q1,q2) = (q1,q2)
                           | otherwise = (p1,p2)

mod11PA.hs:30:30: error:
* Could not deduce (Real (Point a))
    arising from a use of `distance'
  from the context: Real a
    bound by the type signature for:
               closerPair :: Real a => Pair a -> Pair a -> Pair a
    at mod11PA.hs:29:1-50
* In the first argument of `(>)', namely `distance (p1, p2)'
  In the expression: distance (p1, p2) > distance (q1, q2)
  In a stmt of a pattern guard for
                 an equation for `closerPair':
    distance (p1, p2) > distance (q1, q2)

mod11PA.hs:30:30: error:
* Could not deduce (Ord (Point (Point a) -> b0))
    arising from a use of `>'
    (maybe you haven't applied a function to enough arguments?)
  from the context: Real a
    bound by the type signature for:
               closerPair :: Real a => Pair a -> Pair a -> Pair a
    at mod11PA.hs:29:1-50
  The type variable `b0' is ambiguous
  Relevant bindings include
    q2 :: Point a (bound at mod11PA.hs:30:24)
    q1 :: Point a (bound at mod11PA.hs:30:21)
    p2 :: Point a (bound at mod11PA.hs:30:16)
    p1 :: Point a (bound at mod11PA.hs:30:13)
    closerPair :: Pair a -> Pair a -> Pair a (bound at mod11PA.hs:30:1)
* In the expression: distance (p1, p2) > distance (q1, q2)
  In a stmt of a pattern guard for
                 an equation for `closerPair':
    distance (p1, p2) > distance (q1, q2)
  In an equation for `closerPair':
      closerPair (p1, p2) (q1, q2)
        | distance (p1, p2) > distance (q1, q2) = (q1, q2)
        | otherwise = (p1, p2)

Was able to fix my issue by changing the method of closerPair to take in points within two pairs:

closerPair :: Real a => Pair a -> Pair a -> Pair a
closerPair ((x,y),(x1,y1)) ((x2,y2),(x3,y3)) | distance (x,y) (x1,y1) >   distance (x2,y2) (x3,y3) = ((x2,y2),(x3,y3))
                                             | otherwise = ((x,y),(x1,y1))

distance asks for two Pairs, you only feed it one (since you write distance (p1,p2))... So Haskell "complains" that you should give distance a second argument. — Willem Van Onsem
@WillemVanOnsem the distance formula takes two Points, a Pair is 2 points so I'm confused as to why its saying that? Am I missing something/ — jochs02
look at the signatures. distance :: Point a -> Point a -> .. (p1, p2) is not the same as p1 p2 — karakfa
Yup. You're passing distance a pair of points, not passing it a point and another point. You mean distance p1 p2, I think. — Louis Wasserman

leftaroundabout leftaroundabout · Accepted Answer · 2017-03-18T00:19:45

You've already posted a correctly working implementation

closerPair ((x,y),(x1,y1)) ((x2,y2),(x3,y3))
  | distance (x,y) (x1,y1) >   distance (x2,y2) (x3,y3) = ((x2,y2),(x3,y3))
  | otherwise = ((x,y),(x1,y1))

But note that there's no reason to actually pattern-match the Point-coordinates here: you're just putting back x1,y1 and x2,y2... anyway. Thus why not just write it as

closerPair (p₀,p₁) (p₂,p₃)
  | distance p₀ p₁ > distance p₂ p₃ = (p₂,p₃)
  | otherwise                       = (p₀,p₁)

Incidentally, this can be written in terms of standard functions:

import Data.List (minimumBy)
import Data.Ord (comparing)

closerPair v w = minimumBy (comparing $ uncurry distance) [v,w]

Determining closest pair of points using distance function, Haskell

1 Answers