Saturday, April 25, 2009

Solutions to Chapter 3 (p. 70), questions 9-12

(The misnumbering in my printed copy continues, and these wrongly appear as questions 10-13.)

#9. Trivially,

data Direction = LeftTurn | RightTurn | Straight
                 deriving (Show)

I'd use Left and Right, except that there already are constructors of these names defined in Prelude, and the book hasn't yet discussed how to deal with such conflicts.

#10. If the question seems unclear, think of it this way: you're driving from point p1 to point p2; it's a straight line. Now, you have to reach point p3. Do you drive straight on, make a left turn, or make a right turn?

At first it seems this requires lots of trigonometrics to solve, but in fact, there's a simple formula that yields the required result, based on the sign (negative, positive, or zero) of the two vectors defined by the two path segments (p1 to p2 and p2 to p3):

data Point = Point { x :: Double, y :: Double }
             deriving (Show)

turn :: Point -> Point -> Point -> Direction
turn p1 p2 p3 | prod > 0  = LeftTurn
              | prod < 0  = RightTurn
              | otherwise = Straight
     where prod = ((x(p2) - x(p1)) * (y(p3) - y(p1))) - 
                  ((y(p2) - y(p1)) * (x(p3) - x(p1)))

#11. The trick is to define a pattern that extracts the three leading elements of the list. And remember, when progressing to the next step, that you keep two out of these three (rather than considereding all three as "processed").

directions :: [Point] -> [Direction]
directions ps | length ps < 3 = []
directions (p1:p2:p3:ps) = turn p1 p2 p3 : directions (p2:p3:ps)

#12. This is where I draw the line (no pun intended) -- this is too much math before breakfast for me. I might come back to this question later.

4 comments:

  1. Regarding #12, I completely agree, I did exactly the same thing

    ReplyDelete
  2. Thanks for posting this. I was totally stuck on #10. I wondered if you could point me in the direction of how that nifty (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) bit works tho!

    Btw, I think you could clean up #11 a bit a get rid of the guard, and use a wildcard default instead.

    directions :: [Point] -> [Direction]
    directions (p1:p2:p3:ps) =
    direction p1 p2 p3 : directions (p2:p3:ps)
    directions _ = []

    ReplyDelete
  3. Hi Emily,

    The formula is simple computational geometry -- specifically, it's a cross product.

    Nice touch regarding #11!

    ReplyDelete
  4. For #10, the exercise is considering line segments a->b and b->c. So the formula should be corrected accordingly, which I assume it should be (xb-xa)(yc-ya) - (yb-ya)(xc-xa).
    You mistaken p1 as the rotation point.

    ReplyDelete