我几乎完成了 Real World Haskell 的第 3 章。最后一个练习阻止了我。我的代码在运行时会崩溃。有谁可以告诉我代码中的哪一部分有问题？谢谢。
问题：使用前面三个练习中的代码，为一组 2D 点的凸包实现 Graham 扫描算法。您可以在 Wikipedia 上找到关于什么是凸包以及 Graham 扫描算法应该如何工作的详细描述。
回答：
-- Graham Scan, get the convex hull.
-- Implement the algorithm on http://en.wikipedia.org/wiki/Graham_scan
import Data.List
import Data.Ord
data Direction = TurnLeft | TurnRight | GoStraight deriving (Eq, Show)
-- Determine if three points constitute a "left turn" or "right turn" or "go straight".
-- For three points (x1,y1), (x2,y2) and (x3,y3), simply compute the direction of the cross product of the two vectors defined by points (x1,y1), (x2,y2) and (x1,y1), (x3,y3), characterized by the sign of the expression (x2 − x1)(y3 − y1) − (y2 − y1)(x3 − x1). If the result is 0, the points are collinear; if it is positive, the three points constitute a "left turn", otherwise a "right turn".
direction a b c = case compare ((x2 - x1) * (y3 - y1)) ((y2 - y1) * (x3 - x1)) of
EQ -> GoStraight
GT -> TurnLeft
LT -> TurnRight
where x1 = fst a
y1 = snd a
x2 = fst b
y2 = snd b
x3 = fst c
y3 = snd c
grahamScan points = scan (sort points)
-- For each point, it is determined whether moving from the two previously considered points to this point is a "left turn" or a "right turn". If it is a "right turn", this means that the second-to-last point is not part of the convex hull and should be removed from consideration. This process is continued for as long as the set of the last three points is a "right turn". As soon as a "left turn" is encountered, the algorithm moves on to the next point in the sorted array. (If at any stage the three points are collinear, one may opt either to discard or to report it, since in some applications it is required to find all points on the boundary of the convex hull.)
where scan (a : (b : (c : points)))
| (direction a b c) == TurnRight = scan (a : (c : points))
| otherwise = a : (scan (b : (c : points)))
scan (a : (b : [])) = []
-- Put prime to the head.
sort points = prime : (reverse (sortBy (compareByCosine prime) rest))
-- Sort a list to compute. The first step is to find a point whose y-coordinate is lowest. If there are more than one points with lowest y-coordinate, take the one whose x-coordinate is lowest. I name it prime.
where compareByYAndX a b
| compareByY == EQ = comparing fst a b
| otherwise = compareByY
where compareByY = comparing snd a b
prime = minimumBy compareByYAndX points
-- Delete prime from the candidate points. Sort the rest part by the cosine value of the angle between each vector from prime to each point. Reverse it and put prime to the head.
rest = delete prime points
compareByCosine p a b = comparing cosine pa pb
where pa = (fst a - fst p, snd a - snd p)
pb = (fst b - fst p, snd b - snd p)
cosine v = x / sqrt (x ^ 2 + y ^ 2)
where x = fst v
y = snd v