Move History

Rooted by: Find closest point
Fork Selected
  • Code 
    module ClosestPoint (closestPoint) where

import Preloaded (Point,dist)

-- extracts from a list of points the closest to a given point
closestPoint :: Point -> [Point] -> Point
closestPoint _ [] = undefined
closestPoint point (p1 : ps) = snd (foldl fn (dist1, p1) ps) where
  dist1 = dist point p1
  fn (dist1, p1) p2 | dist1 < dist2 = (dist1, p1) | otherwise = (dist2, p2) where
    dist2 = dist point p2
    Preloaded Code 
    module Preloaded (Point,dist) where

type Point = (Float, Float)

-- calculates the ditance between two points
dist :: Point -> Point -> Float
dist (x1, x2) (y1, y2)
  = sqrt (dx * dx + dy * dy)
  where (dx, dy) = (y1 - x1, y2 - x2)
     Test Cases 
    module ClosestPointSpec (spec) where

import ClosestPoint (closestPoint)
import Preloaded (Point)
import Test.Hspec
import Test.QuickCheck

spec :: Spec
spec = do
  it "fixed tests" $ do
    let points = [(38, 19), (833, 938), (83, 49), (83, 83), (72, 15)]
    closestPoint (0, 0) points `shouldBe` (38, 19)
  it "random tests" $ do
    property $ \ point (NonEmpty points) -> do
      let actual   =    closestPoint point points
          expected = refClosestPoint point points
      actual `shouldSatisfy` (`elem` points)
      actual `shouldBe` expected

refClosestPoint :: Point -> [Point] -> Point
refClosestPoint point [p] = p
refClosestPoint point (p : ps) = closest point p (refClosestPoint point ps) where
  closest :: Point -> Point -> Point -> Point
  closest point p1 p2 | dist point p1 < dist point p2 = p1 | otherwise = p2

-- local copy, so we may change `Preloaded.dist` - maybe for a counting copy - without affecting `refClosestPoint`

-- calculates the ditance between two points
dist :: Point -> Point -> Float
dist (x1, x2) (y1, y2) = sqrt (dx * dx + dy * dy) where (dx, dy) = (y1 - x1, y2 - x2)
    View Run Output
  • Code
    • module ClosestPoint (closestPoint) where
    • import Preloaded (Point,dist)
    • -- extracts from a list of points the closest to a given point
    • closestPoint :: Point -> [Point] -> Point
    • closestPoint point [] = undefined
    • closestPoint point (p:ps) = closest (dist point p) p ps where
    • closest :: Float -> Point -> [Point] -> Point
    • closest dist1 p1 [] = p1
    • closest dist1 p1 (p2:ps) | dist1 < dist2 = closest dist1 p1 ps
    • | otherwise = closest dist2 p2 ps
    • where dist2 = dist point p2
    • closestPoint _ [] = undefined
    • closestPoint point (p1 : ps) = snd (foldl fn (dist1, p1) ps) where
    • dist1 = dist point p1
    • fn (dist1, p1) p2 | dist1 < dist2 = (dist1, p1) | otherwise = (dist2, p2) where
    • dist2 = dist point p2