4
\$\begingroup\$

I have recently started learning functional programming and Haskell. I have encountered this problem:

Consider three two-dimensional points a, b, and c. If we look at the angle formed by the line segment from a to b and the line segment from b to c, it either turns left, turns right, or forms a straight line. Define a Direction data type that lets you represent these possibilities. Write a function that calculates the turn made by three 2D points and returns a Direction.

I have heard that one of the goals of the Haskell language is to create elegant solutions.

This is my solution:

data Direction = LeftTurn | RightTurn | Straight deriving Show

findDirection (x, y) (x1, y1) (x2, y2) 
    | (x, y) == (x1, y1)          = Straight
    | (x1, y1) == (x2, y2)        = Straight
    | (x, y) == (x2, y2)          = Straight
    | x == x1 && x1 == x2         = Straight
    | x1 == x && y1 > y && x2 > x = RightTurn
    | x1 == x && y1 > y && x2 < x = LeftTurn
    | x1 == x && y1 < y && x2 < x = RightTurn
    | x1 == x && y1 < y && x2 > x = LeftTurn
    | x1 > x && y2 > y_on_line    = LeftTurn
    | x1 > x && y2 < y_on_line    = RightTurn
    | x1 > x && y2 == y_on_line   = Straight
    | x1 < x && y2 > y_on_line    = RightTurn
    | x1 < x && y2 < y_on_line    = LeftTurn
    | x1 < x && y2 == y_on_line   = Straight
   where y_on_line   = slope * x2 + y_intercept
         slope       = (y1 - y) / (x1 - x)
         y_intercept = y - slope * x

This looks like it is too long to be considered an elegant solution.

\$\endgroup\$
  • 1
    \$\begingroup\$ Think about a planar cross product and its sign. \$\endgroup\$ – vnp Oct 21 '18 at 1:10
  • \$\begingroup\$ This looks like a very complicated solution to a simple problem. Welcome to Code Review! \$\endgroup\$ – Mast Oct 21 '18 at 7:55
  • \$\begingroup\$ Follow-up question \$\endgroup\$ – 200_success Oct 22 '18 at 14:23
  • \$\begingroup\$ As a general rule of thumb, lots of guards for a single function is probably not an elegant solution. \$\endgroup\$ – Code-Guru Oct 23 '18 at 3:27
5
\$\begingroup\$

Welcome to Haskell (and Code Review). Your ADT Direction is a good approach for the result. However, top-level functions should have a type, as it will make type errors easier to read and give other users an idea how to use your function:

type Point2 = (Double, Double)

findDirection :: Point2 -> Point2 -> Point2 -> Direction    
findDirection (x, y) (x1, y1) (x2, y2)

While isn't necessary—GHC can infer it—it can at least act as a minimal documentation.

Next, we should tackle the names. We have x, x1 and x2. Those seem arbitrary. Why don't we start with x1? The names (ax,ay), (bx,by) and (cx,cy) would be more suitable, since we're talking about the coordinates of three specific points, a, b and c:

findDirection :: Point2 -> Point2 -> Point2 -> Direction    
findDirection (ax, ay) (bx, by) (cx, cy)

However, as vnp said, you should use the cross product. While the cross-product is only defined for three dimensions, we can simply embed your points into \$\mathbb R^3\$ and then take the Z-component of the resulting vector:

type Vector2 = (Double, Double)

-- See https://en.wikipedia.org/wiki/Cross_product#Computing_the_cross_product
cross :: Vector2 -> Vector2 -> Double
cross (ax, ay) (bx, by) = error "Implement this as an exercise"

With yet another function, we can then get the two vectors from our original three points:

diff :: Point2 -> Point2 -> Vector2
diff (ax, ay) (bx, by) = (bx - ax, by - ay)

Now we really end up with an elegant solution:

findDirection :: Point2 -> Point2 -> Point2 -> Direction
findDirection a b c = 
    case cross (a `diff` b) (b `diff` c) `compare` 0 of
        GT -> LeftTurn
        EQ -> Straight
        LT -> RightTurn
\$\endgroup\$
4
\$\begingroup\$

This is not a review, but an extended comment.

I have heard that one of the goals of the Haskell language is to create elegant solutions.

It seems like a major misconception. The elegance of the solution does not depend on the language. The language does not create solutions, it only codifies them. It the approach taken is wrong, the language is powerless.

Unfortunately, the approach taken here is wrong. You need to recall some math before diving in.

The direction in question is characterized by the sign of a cross product of \$b - a\$ and \$c - b\$. It is a left turn if the cross product is positive, a right turn if it is negative, and a straight line if it is zero.

That said, your code fails badly when x1 - x happens to be zero. That alone should raise your doubt in the correctness of the approach.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.