[Haskell-beginners] Parse error in pattern

7 Jan 2012

      Hi,

I am writing a Graham Scan function. What puzzles me is it cannot be compiled. Does anyone know what is wrong with "scan"? Thanks.

==== compile ====
bogon% ghc GrahamScan.hs                                                                                             -- NORMAL --
[1 of 1] Compiling Main             ( GrahamScan.hs, GrahamScan.o )

GrahamScan.hs:30:1: Parse error in pattern: scan
==== compile ====

==== code ====
data Point a = Point {
    x :: a,
    y :: b
}

instance Ord (Point a) where
    compare (Point x1 y1) (Point x2 y2) = compare (y1, x1) (y2, x2)

data Vector a = Vector {
    start   :: Point a,
    end     :: Point a
}

cosine :: Vector a -> Ratio a
cosine (Vector (Point x1 y1) (Point x2 y2)) = (x2 - x1) / ((x2 - x1) ^ 2 + (y2 - y1) ^ 2)

instance Ord (Vector a) where
    compare a b = compare (f a) (f b) where
        f = negate . cosine

sort' :: [Point a] -> [Point a]
sort' xs = minPoint : fmap end sortedVectors where
    sortedVectors   = sort $ map (Vector minPoint) $ delete minPoint xs
    minPoint        = minimum xs

ccw :: Point a -> Point a -> Point a -> Bool
ccw (Point x1 y1) (Point x2 y2) (Point x3 y3) = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) > 0

scan :: [Point a] -> [Point a]
scan p1 : p2 : p3 : xs
    | ccw p1 p2 p3  = p1 : scan (p2 : p3 : xs)
    | otherwise     = scan (p1 : p3 : xs)
scan xs = xs

grahamScan :: [Point a] -> [Point a]
grahamScan = scan . sort'
==== code ====

Best regards,
Zhi-Qiang Lei
zhiqiang.lei@gmail.com