When reviewing a Graham scan convex hull algorithm implementation, I wrote the following function in an answer:
giftWrap :: [Vector2] -> [Vector2] giftWrap vs = result where -- Decides whether to keep or reject vertex b. -- Vertex b is provisionally kept if a left turn occurs there; the result -- is finalized only when a closed left-turn-only tour is completed. giftWrap' (a:b:c:vs) | vs ==  && dir == TurnLeft = (True, [b, c]) | vs ==  = (False, [c]) | dir == TurnLeft && final = (True, (b:gw)) | dir == TurnLeft = giftWrap' (a:gw) | otherwise = (False, (a : c : vs)) where dir = turn a b c (final, gw) = giftWrap' (b:c:vs) (_, result) = giftWrap' (vs ++ [head vs])
The purpose of this function is to keep only the vertices in the input sequence at which a left turn occurs. However, if a right turn is encountered, we must drop the right-turn vertex from consideration, backtrack, and try again.
To achieve backtracking, I've designed the inner function to return a status flag in addition to the result. I'm not satisfied with it though, as it looks ugly and is hard to follow.
Is there a better way to implement recursion with possible backtracking?
Is recursion the appropriate technique to use in the first place?