Implementation of Graham Scan algorithm in Haskell Here is an implementation of Graham Scan algorithm for computing the convex hull of a finite set of points:

data Point = Point {
  xcoord :: Double,
  ycoord :: Double
} deriving (Show)

data Direction = ToRight | Straight | ToLeft  deriving (Show, Eq)

distance :: Point -&gt; Point -&gt; Double
distance a b = sqrt (((xcoord a) - (xcoord b))^2 + ((ycoord a) - (ycoord b))^2)

-- The direction function can be simplified after some algebraic analysis:
direction :: Point -&gt; Point -&gt; Point -&gt; Direction
direction a b c
  | s &lt; 0 = ToRight
  | s == 0 = Straight
  | s &gt; 0 = ToLeft
  where
    s = ((xcoord c) - (xcoord a)) * ((ycoord a) - (ycoord b)) + ((ycoord c) - (ycoord a)) * ((xcoord b) - (xcoord a))

directions_ :: [Point] -&gt; [Direction]
directions_ [] = []
directions_ [_] = []
directions_ [_, _] = []
directions_ (a:b:c:xs) = (direction a b c) : (directions_ (b:c:xs))

directions :: [Point] -&gt; [Direction]
directions xs = ToLeft : ToLeft : (directions_ xs)


lowestYPoint :: [Point] -&gt; Point
lowestYPoint [x] = x
lowestYPoint (x:xs)
  | (ycoord x) &lt;= (ycoord lowestRest) = x
  | otherwise = lowestRest
  where
    lowestRest = lowestYPoint xs


cosineAB :: Point -&gt; Point -&gt; Double
cosineAB a b = ((xcoord b) - (xcoord a)) / (distance a b)

sortByAngle :: Point -&gt; [Point] -&gt; [Point]
sortByAngle x xs = sortBy comparePoints xs where
  comparePoints :: Point -&gt; Point -&gt; Ordering
  comparePoints a b
    | cA &gt; cB = LT
    | cA &lt; cB = GT
    | otherwise = case () of
      _ | xA &lt; xB  -&gt; LT
        | xA &gt; xB  -&gt; GT
        | xA == xB -&gt; case () of
          _ | yA &lt; yB   -&gt; LT
            | yA &gt; yB   -&gt; GT
            | yA == yB  -&gt; EQ
    where
      yA = (ycoord a)
      yB = (ycoord b)
      xA = (xcoord a)
      xB = (xcoord b)
      cA = (cosineAB x a)
      cB = (cosineAB x b)

grahamScanDirections :: [Direction] -&gt; [Bool]
grahamScanDirections [] = []
grahamScanDirections [_] = [True]
grahamScanDirections (ToLeft:ToRight:xs) = False : (grahamScanDirections (ToLeft:xs))
grahamScanDirections (ToLeft:ToLeft:xs)  = True  : (grahamScanDirections (ToLeft:xs))
grahamScanDirections (ToLeft:Straight:xs) = False : (grahamScanDirections (ToLeft:xs))
grahamScanDirections _ = error "Impossible scenario"

filterByList :: [Bool] -&gt; [a] -&gt; [a]
filterByList [] _ = []
filterByList _ [] = []
filterByList (x:xs) (y:ys)
  | x = y : (filterByList xs ys)
  | otherwise = (filterByList xs ys)

grahamScan :: [Point] -&gt; [Point]
grahamScan ps = filterByList bool_list ps1 where
  -- sort ps by their angles (or cosine values) formed with the lowest point
  ps1 = sortByAngle (lowestYPoint ps) ps
  bool_list = grahamScanDirections $ directions ps1


Test:

*Main&gt; let ps = [(Point 1 0), (Point 1 2), (Point 0 3), (Point 2 3), (Point 2 2), (Point 3 2), (Point 2 1)]
*Main&gt; grahamScan ps
[Point {xcoord = 1.0, ycoord = 0.0},Point {xcoord = 3.0, ycoord = 2.0},Point {xcoord = 2.0, ycoord = 3.0},Point {xcoord = 0.0, ycoord = 3.0}]


Any suggestion about correctness/performance or any other possible improvement is appreciated.
Here are some improvements you may apply.

You can combine pattern matching and records. It allows you to avoid unnecessary numerous calls to xcoord and ycoord. It also makes your code easier to read.

You can force strictness on xcoord and ycoord fields.

These two improvements help with performance.

You can also do the following:


simplify pattern matching py reordering the patterns (see filterByList)
drop lots of parenthesis since space has bigger precedence than operators
simplify comparePoints with keeping only one level of guards
use more standard library functions (see lowestYPoint)


Most of these were given to me by hlint ;-)

import Data.List
import Data.Function (on)
import Control.DeepSeq

data Point = Point {
    xcoord :: !Double,
    ycoord :: !Double
} deriving Show

data Direction = ToRight | Straight | ToLeft  deriving (Show, Eq)

distance :: Point -&gt; Point -&gt; Double
distance (Point xA yA) (Point xB yB) = sqrt ((xA - xB)^2 + (yA - yB)^2)

direction :: Point -&gt; Point -&gt; Point -&gt; Direction
direction (Point xA yA) (Point xB yB) (Point xC yC)
    | s &lt;  0    = ToRight
    | s == 0    = Straight
    | otherwise = ToLeft
    where
        s = (xC - xA) * (yA - yB) + (yC - yA) * (xB - xA)

directions_ :: [Point] -&gt; [Direction]
directions_ (a:b:c:xs) = direction a b c : directions_ (b:c:xs)
directions_ _ = []

directions :: [Point] -&gt; [Direction]
directions xs = ToLeft : ToLeft : directions_ xs

lowestYPoint :: [Point] -&gt; Point
lowestYPoint = minimumBy (compare `on` ycoord)

cosineAB :: Point -&gt; Point -&gt; Double
cosineAB a@(Point xA _) b@(Point xB _) = (xB - xA) / distance a b

comparePoints :: Point -&gt; Point -&gt; Point -&gt; Ordering
comparePoints x a@(Point xA yA) b@(Point xB yB)
    | cA &gt; cB   = LT
    | cA &lt; cB   = GT
    | xA &lt; xB   = LT
    | xA &gt; xB   = GT
    | yA &lt; yB   = LT
    | yA &gt; yB   = GT
    | otherwise = EQ
    where
        cA = cosineAB x a
        cB = cosineAB x b

sortByAngle :: Point -&gt; [Point] -&gt; [Point]
sortByAngle x = sortBy (comparePoints x)

grahamScanDirections :: [Direction] -&gt; [Bool]
grahamScanDirections [] = []
grahamScanDirections [_] = [True]
grahamScanDirections (ToLeft:ToRight:xs) = False : grahamScanDirections (ToLeft:xs)
grahamScanDirections (ToLeft:ToLeft:xs)  = True  : grahamScanDirections (ToLeft:xs)
grahamScanDirections (ToLeft:Straight:xs) = False : grahamScanDirections (ToLeft:xs)
grahamScanDirections _ = error "Impossible scenario"

filterByList :: [Bool] -&gt; [a] -&gt; [a]
filterByList (True :xs) (y:ys) = y : filterByList xs ys
filterByList (False:xs) (_:ys) = filterByList xs ys
filterByList _ _               = []

grahamScan :: [Point] -&gt; [Point]
grahamScan ps = filterByList bool_list ps1
    where ps1       = sortByAngle (lowestYPoint ps) ps
          bool_list = grahamScanDirections $ directions ps1

pss = replicate 1000000
                [ Point 1 0
                , Point 1 2
                , Point 0 3
                , Point 2 3
                , Point 2 2
                , Point 3 2
                , Point 2 1
                ]

instance NFData Point where
    rnf a = a `seq` () 

main = (map grahamScan pss) `deepseq` putStrLn "Done"