<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div apple-content-edited="true"><span class="Apple-style-span" style="orphans: 2; text-indent: 0px; widows: 2; -webkit-text-decorations-in-effect: none; "><div style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; ">I think I find what the problem is:</div><div style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><br></div><div><ol class="MailOutline"><li>When calculating the distance in cosine function, a sqrt is missing.</li><li>There is no pivot append to the sorted list of points in sort'.</li><li>The algorithm which scan implement is incorrect. Read more details in my comments.</li></ol></div><div style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><br></div><div style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; ">I appreciate you all.</div><div style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><br></div><div><div>=== prop_scan_idempotent on GrahamScan_qc.hs:8 ===</div><div>+++ OK, passed 100 tests.</div></div><div style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><br></div><div style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; ">=== Code ===</div><div><div>module GrahamScan (grahamScan, Point(..))</div><div>where</div><div><br></div><div>import Data.List</div><div>import Data.Ratio</div><div><br></div><div>data Point = Point {</div><div> x :: Double,</div><div> y :: Double</div><div>} deriving (Eq, Show)</div><div><br></div><div>instance Ord Point where</div><div> compare (Point x1 y1) (Point x2 y2) = compare (y1, x1) (y2, x2)</div><div><br></div><div>data Vector = Vector {</div><div> start :: Point,</div><div> end :: Point</div><div>} deriving (Eq)</div><div><br></div><div>cosine :: Vector -> Double</div><div>cosine (Vector (Point x1 y1) (Point x2 y2)) = (x2 - x1) / distance where</div><div> distance = sqrt $ (x2 - x1) ^ 2 + (y2 - y1) ^ 2</div><div><br></div><div>instance Ord Vector where</div><div> compare a b = compare (f a) (f b) where</div><div> f = negate . cosine</div><div><br></div><div>-- After sorting a pivot should be append to the sorted list impermanently.</div><div>-- Otherwise the last point could not be examine.</div><div>sort' :: [Point] -> [Point]</div><div>sort' xs = pivot : fmap end sortedVectors ++ [pivot] where</div><div> sortedVectors = sort . fmap (Vector pivot) . delete pivot $ xs</div><div> pivot = minimum xs</div><div><br></div><div>isCounterClockwise :: Point -> Point -> Point -> Bool</div><div>isCounterClockwise (Point x1 y1) (Point x2 y2) (Point x3 y3) = (x2 - x1) * (y3 - y1) > (y2 - y1) * (x3 - x1)</div><div><br></div><div>-- When a point is considered clockwise or collinear, just removing it</div><div>-- is not enough, the point before it has to be re-examined. Or else,</div><div>-- the function is not idempotent. This is not mentioned on Wikipedia.</div><div>scan' :: ([Point], [Point]) -> ([Point], [Point])</div><div>scan' (p1 : p2 : p3 : xs, ys)</div><div> | isCounterClockwise p1 p2 p3 = scan' (p2 : p3 : xs, ys ++ [p1])</div><div> | otherwise = scan' (last ys : p1 : p3 : xs, init ys)</div><div>scan' (xs, ys) = ([], ys ++ xs)</div><div><br></div><div>-- The last point is pivot, ignore it in result.</div><div>scan :: [Point] -> [Point]</div><div>scan xs = init . (\(_, ys) -> ys) . scan' $ (xs, [])</div><div><br></div><div>grahamScan :: [Point] -> [Point]</div><div>grahamScan xs@(_ : _ : _ : _) = scan . sort' . nub $ xs</div></div><div style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; ">=== Code ===</div><div style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><br class="Apple-interchange-newline">Best regards,<br class="Apple-interchange-newline">Zhi-Qiang Lei</div><div style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><a href="mailto:zhiqiang.lei@gmail.com">zhiqiang.lei@gmail.com</a></div></span>
</div>
<br></body></html>