<p>Typo /counterwise/ - counterclockwise.</p>
<p>BTW, the 'cosine's functionalty can be replaced by the outer product.<br>
</p>
<div class="gmail_quote">2012-1-8 下午11:54 於 "Ray Song" <<a href="mailto:emacsray@gmail.com" target="_blank">emacsray@gmail.com</a>> 寫道：<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<p>The 'scan' is flawed. A counterwise angle formed by the first three points does not guarantee p1's existence in the hull.<br>
2012-1-8 下午3:32 於 "Zhi-Qiang Lei" <<a href="mailto:zhiqiang.lei@gmail.com" target="_blank">zhiqiang.lei@gmail.com</a>> 寫道：<br>
><br>
> Hi,<br>
><br>
> The Graham Scan function I wrote, looks like running well. But when I put it in QuickCheck, it just failed in some case. Anyone can show me some clues about the problem? Thanks.<br>
><br>
> When I test it in ghci with some example, it returns the right result.<br>
> *Main> let xs = [Point {x = 1.0, y = 1.0},Point {x = 0.0, y = 4.0},Point {x = 0.0, y = 6.0},Point {x = 3.0, y = 5.0},Point {x = 4.0, y = 4.0},Point {x = 4.0, y = 1.0},Point {x = 3.0, y = 3.0},Point {x = 2.0, y = 2.0},Point {x = 5.0, y = 5.0}]<br>
> *Main> grahamScan xs<br>
> [Point {x = 1.0, y = 1.0},Point {x = 4.0, y = 1.0},Point {x = 5.0, y = 5.0},Point {x = 0.0, y = 6.0},Point {x = 0.0, y = 4.0}]<br>
> *Main> grahamScan it<br>
> [Point {x = 1.0, y = 1.0},Point {x = 4.0, y = 1.0},Point {x = 5.0, y = 5.0},Point {x = 0.0, y = 6.0},Point {x = 0.0, y = 4.0}]<br>
><br>
> However, QuickCheck find some points which can fail it. Could it be a data type overflow problem?<br>
><br>
> prop_scan_idempotent xs = not (null xs) ==> (grahamScan . grahamScan) xs == grahamScan xs<br>
><br>
> *Main> quickCheck prop_scan_idempotent<br>
> *** Failed! Falsifiable (after 13 tests and 4 shrinks):<br>
> [Point {x = -6.29996952110807, y = -91.37172300100718},Point {x = 9.353314917365527, y = 64.35532141764591},Point {x = -23.826685687218355, y = 60.32049750442556},Point {x = -1.4281411275074123, y = 31.54197550020998},Point {x = -2.911218918860731, y = 15.564623822256719}]<br>
><br>
> === code ===<br>
> module GrahamScan (grahamScan, Point(..))<br>
> where<br>
><br>
> import Data.List<br>
> import Data.Ratio<br>
><br>
> data Point = Point {<br>
> x :: Double,<br>
> y :: Double<br>
> } deriving (Eq, Show)<br>
><br>
> instance Ord Point where<br>
> compare (Point x1 y1) (Point x2 y2) = compare (y1, x1) (y2, x2)<br>
><br>
> data Vector = Vector {<br>
> start :: Point,<br>
> end :: Point<br>
> } deriving (Eq)<br>
><br>
> cosine :: Vector -> Double<br>
> cosine (Vector (Point x1 y1) (Point x2 y2)) = (x2 - x1) / ((x2 - x1) ^ 2 + (y2 - y1) ^ 2)<br>
><br>
> instance Ord Vector where<br>
> compare a b = compare (f a) (f b) where<br>
> f = negate . cosine<br>
><br>
> sort' :: [Point] -> [Point]<br>
> sort' xs = pivot : fmap end sortedVectors where<br>
> sortedVectors = sort . fmap (Vector pivot) . delete pivot $ xs<br>
> pivot = minimum xs<br>
><br>
> counterClockwise :: Point -> Point -> Point -> Bool<br>
> counterClockwise (Point x1 y1) (Point x2 y2) (Point x3 y3) = (x2 - x1) * (y3 - y1) > (y2 - y1) * (x3 - x1)<br>
><br>
> scan :: [Point] -> [Point]<br>
> scan (p1 : p2 : p3 : xs)<br>
> | counterClockwise p1 p2 p3 = p1 : scan (p2 : p3 : xs)<br>
> | otherwise = scan (p1 : p3 : xs)<br>
> scan xs = xs<br>
><br>
> grahamScan :: [Point] -> [Point]<br>
> grahamScan = scan . sort' . nub<br>
> === code ===<br>
><br>
><br>
> Best regards,<br>
> Zhi-Qiang Lei<br>
> <a href="mailto:zhiqiang.lei@gmail.com" target="_blank">zhiqiang.lei@gmail.com</a><br>
><br>
><br>
> _______________________________________________<br>
> Beginners mailing list<br>
> <a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
> <a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
</p>
</blockquote></div>