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 : [])) = []
What error message do you get? I loaded this code into ghci verbatim (modulo a module declaration) and it worked fine, no errors. However the definitions don't seem to be quite right. Consider any set of 3 non-linear points. Trivially the convex hull of that set is the set itself. Look at what your function scan does for a set of three points. It only returns 2, which can't be right.