<p>The &#39;scan&#39; is flawed. A counterwise angle formed by the first three points does not guarantee p1&#39;s existence in the hull.<br>
2012-1-8 ¤U¤Č3:32 ©ó &quot;Zhi-Qiang Lei&quot; &lt;<a href="mailto:zhiqiang.lei@gmail.com">zhiqiang.lei@gmail.com</a>&gt; ĽgąDˇG<br>
&gt;<br>
&gt; Hi,<br>
&gt;<br>
&gt; 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>
&gt;<br>
&gt; When I test it in ghci with some example, it returns the right result.<br>
&gt; *Main&gt; 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>

&gt; *Main&gt; grahamScan xs<br>
&gt; [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>
&gt; *Main&gt; grahamScan it<br>
&gt; [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>
&gt;<br>
&gt; However, QuickCheck find some points which can fail it. Could it be a data type overflow problem?<br>
&gt;<br>
&gt; prop_scan_idempotent xs = not (null xs) ==&gt; (grahamScan . grahamScan) xs == grahamScan xs<br>
&gt;<br>
&gt; *Main&gt; quickCheck prop_scan_idempotent<br>
&gt; *** Failed! Falsifiable (after 13 tests and 4 shrinks):<br>
&gt; [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>

&gt;<br>
&gt; === code ===<br>
&gt; module GrahamScan (grahamScan, Point(..))<br>
&gt; where<br>
&gt;<br>
&gt; import Data.List<br>
&gt; import Data.Ratio<br>
&gt;<br>
&gt; data Point = Point {<br>
&gt; &nbsp; &nbsp;x :: Double,<br>
&gt; &nbsp; &nbsp;y :: Double<br>
&gt; } deriving (Eq, Show)<br>
&gt;<br>
&gt; instance Ord Point where<br>
&gt; &nbsp; &nbsp;compare (Point x1 y1) (Point x2 y2) = compare (y1, x1) (y2, x2)<br>
&gt;<br>
&gt; data Vector = Vector {<br>
&gt; &nbsp; &nbsp;start &nbsp; :: Point,<br>
&gt; &nbsp; &nbsp;end &nbsp; &nbsp; :: Point<br>
&gt; } deriving (Eq)<br>
&gt;<br>
&gt; cosine :: Vector -&gt; Double<br>
&gt; cosine (Vector (Point x1 y1) (Point x2 y2)) = (x2 - x1) / ((x2 - x1) ^ 2 + (y2 - y1) ^ 2)<br>
&gt;<br>
&gt; instance Ord Vector where<br>
&gt; &nbsp; &nbsp;compare a b = compare (f a) (f b) where<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp;f = negate . cosine<br>
&gt;<br>
&gt; sort&#39; :: [Point] -&gt; [Point]<br>
&gt; sort&#39; xs = pivot : fmap end sortedVectors where<br>
&gt; &nbsp; &nbsp;sortedVectors &nbsp; = sort . fmap (Vector pivot) . delete pivot \$ xs<br>
&gt; &nbsp; &nbsp;pivot &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; = minimum xs<br>
&gt;<br>
&gt; counterClockwise :: Point -&gt; Point -&gt; Point -&gt; Bool<br>
&gt; counterClockwise (Point x1 y1) (Point x2 y2) (Point x3 y3) = (x2 - x1) * (y3 - y1) &gt; (y2 - y1) * (x3 - x1)<br>
&gt;<br>
&gt; scan :: [Point] -&gt; [Point]<br>
&gt; scan (p1 : p2 : p3 : xs)<br>
&gt; &nbsp; &nbsp;| counterClockwise p1 p2 p3 = p1 : scan (p2 : p3 : xs)<br>
&gt; &nbsp; &nbsp;| otherwise &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; = scan (p1 : p3 : xs)<br>
&gt; scan xs = xs<br>
&gt;<br>
&gt; grahamScan :: [Point] -&gt; [Point]<br>
&gt; grahamScan = scan . sort&#39; . nub<br>
&gt; === code ===<br>
&gt;<br>
&gt;<br>
&gt; Best regards,<br>
&gt; Zhi-Qiang Lei<br>
&gt; <a href="mailto:zhiqiang.lei@gmail.com">zhiqiang.lei@gmail.com</a><br>
&gt;<br>
&gt;<br>
&gt; _______________________________________________<br>
&gt; Beginners mailing list<br>