Graham Scan Implementation in Haskell

graham_scan.hs

import Data.List
import Data.List.Split
import Data.Ord
import System.Environment

theta :: (Num a, Eq a, Ord a, Fractional a) => (a,a) -> (a,a) -> a
theta (x1,y1) (x2,y2)
  | dx == 0 && dy == 0 = 0
  | dx < 0 = 2 - t
  | dy < 0 = 4 + t
  | otherwise = t
  where dx = x2 - x1
        dy = y2 - y1
        t = dy / (abs dx + abs dy)

minPoint :: (Ord a) => [(a,a)] -> (a,a)
minPoint [a] = a
minPoint ((x,y):xs)
  | y == (snd other) = (minX (x,y) other)
  | y < (snd other) = (x,y)
  | otherwise = other
  where other = (minPoint xs)
        minX (x,y) (x1,y1)
          | x > x1 = (x,y)
          | otherwise = (x1,y1)

onLeft s e pt = (side s e pt) > 0
  where side (x,y) (x1,y1) (x2, y2) = (x1 - x) * (y2 - y) - (y1 - y) * (x2 - x)

stringify list sep = (foldl section "" (init list))++(show (last list))
  where section p i = p++(show i)++sep

tuplify strs = map split (filter (/= "") strs)
  where split str = tuple (splitOn " " str)
        tuple (a:b:[]) = (floatify a,floatify b)
        floatify i = read i :: Float

merge [] item = [item]
merge (a:[]) item = [item, a]
merge stack@(e:s:_) pt = if onLeft (snd s) (snd e) (snd pt)
  then (pt:stack)
  else merge (tail stack) pt

getHull list = reverse (foldl (merge) [] sorted)
  where anchor = minPoint list
        sorted = sortBy (comparing (\(_,a) -> theta anchor a)) (zip [0..] list)

main = do
  args <- getArgs
  file <- readFile (head args)
  let pts = tuplify.tail.(splitOn "\n") $ file
      in putStrLn $ stringify ((map fst) $ getHull pts) " "