[Haskell-beginners] Graham Scan exercise from Chapter 3 RWH -Spoilers. Don't read if you want to do this exercise.

[Angel de Vicente]

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