[Haskell-beginners] Graham Scan exercise from Chapter 3 RWH
-Spoilers. Don't read if you want to do this exercise.
Angel de Vicente
angelv at iac.es
Tue Sep 7 05:15:13 EDT 2010
Hi Michael,
On 03/09/10 01:21, Michael Litchard wrote:
> Below is my solution for the Graham Scan Algorithm.
> I tried to limit myself to information in the first three chapters
> while completing this problem.
> Now, I want to remove the explicit recursion and use more idiomatic
> Haskell. I'd like to get some advice on which functions/modules would
> be helpful in this.
This is not really what you ask for, but I thought I would point out
that you code seems to have either a bug or it doesn't implement the
Graham Scan algorithm correctly. For example, when we change the points to
[(10,0),
(10,1),(-10,1),(-10,0),(-7,0),(-10,2),(-10,3),(-4,1),(-2,2),(-12,1)]
your code gives as the solution:
*Main> main
[(10.0,0.0),(10.0,1.0),(-10.0,1.0),(-10.0,0.0),(-7.0,0.0),(10.0,1.0),(-4.0,1.0)]
while the correct solution has only 5 points
[(-10,0),(10,0),(10,1),(-10,3),(-12,1)]
Yo can see my solution to this exercise at
http://angel-de-vicente.blogspot.com/2010/06/graham-scan-in-haskell.html
Cheers,
Ángel de Vicente
>
>
> <code>
> data Direction = DStraight
> | DLeft
> | DRight
> deriving (Eq,Show)
>
> type PointXY = (Double,Double)
>
> calcTurn :: PointXY -> PointXY -> PointXY -> Direction
> calcTurn a b c
> | crossProduct == 0 = DStraight
> | crossProduct> 0 = DLeft
> | otherwise = DRight
> where crossProduct = ((fst b - fst a) * (snd c - snd a)) -
> ((snd b - snd a) * (fst c - fst a))
>
> calcDirectionList :: [PointXY] -> [Direction]
> calcDirectionList (x:y:z:zs) = (calcTurn x y z) : (calcDirectionList (y:z:zs))
> calcDirectionList _ = []
>
> sortListByY :: [PointXY] -> [PointXY]
> sortListByY [] = []
> sortListByY [a] = [a]
> sortListByY (a:as) = insert (sortListByY as)
> where insert [] = [a]
> insert (b:bs) | snd a<= snd b = a : b : bs
> | otherwise = b : insert bs
>
> sortListByCoTangent :: [PointXY] -> [PointXY]
> sortListByCoTangent [] = []
> sortListByCoTangent [a] = [a]
> sortListByCoTangent (a:as) = a : insert (sortListByCoTangent as)
> where insert :: [PointXY] -> [PointXY]
> insert [b] = [b]
> insert (b:c:cs) | (myCoTan a b)>= (myCoTan a
> c) = b : insert (c:cs)
> | otherwise
> = c : insert (b:cs)
> where myCoTan :: PointXY -> PointXY -> Double
> myCoTan p1 p2 = (fst p2 - fst p1) /
> (snd p2 - snd p1)
>
>
> createHull :: [PointXY] -> [PointXY]
> createHull (a:b:c:cs) = a : filterPoint (createHull (b:c:cs))
> where filterPoint :: [PointXY] -> [PointXY]
> filterPoint (x:y:z:zs)
> | calcTurn x y z == (DLeft) = [x] ++ [y]
> ++ [z] ++ filterPoint (zs)
> | otherwise = [x] ++ [z]
> ++ filterPoint (zs)
> filterPoint [x] = a:[x]
> filterPoint _ = []
> createHull _ = []
>
> main :: IO ()
> main = do
> let points = [(5.0,0.0),(5.0,6.0),(3.0,-4.2),(0.0,6.0)]
> print $ createHull points
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
--
http://www.iac.es/galeria/angelv/
High Performance Computing Support PostDoc
Instituto de Astrofísica de Canarias
---------------------------------------------------------------------------------------------
ADVERTENCIA: Sobre la privacidad y cumplimiento de la Ley de Protección de Datos, acceda a http://www.iac.es/disclaimer.php
WARNING: For more information on privacy and fulfilment of the Law concerning the Protection of Data, consult http://www.iac.es/disclaimer.php?lang=en
More information about the Beginners
mailing list