Функция сортировки, похоже, не разрушает связи

Question

Я только начал изучать Haskell. Я занимаюсь упражнениями «Real World Haskell», глава 3, и я в тупике о поведении, которое я не понимаю.

Я не понимаю, почему мой grahamSort, кажется, не нарушает связь должным образом. Функция сначала находит контрольную точку P (через grahamGetFirstCandidate), затем сортирует другие точки в соответствии с углом их и P с осью x. Я использую (минус) косинус в качестве прокси для угла.
grahamGetFirstCandidate похоже работает как ожидалось.

код (жаль, что это, вероятно, не очень чистый):

import Data.List as List 

data TwoD = TwoD { 
x :: Float, 
y :: Float 
} deriving (Show, Eq) 

dotProduct :: TwoD -> TwoD -> Float 
dotProduct (TwoD xa ya) (TwoD xb yb) = xa * xb + ya * yb 

grahamGetFirstCandidate :: [TwoD] -> TwoD 
grahamGetFirstCandidate [] = error "Trying to find point with minimum y in empty List" 
grahamGetFirstCandidate (p:ps) = search p ps where 
    search :: TwoD -> [TwoD] -> TwoD 
    search pmin [] = pmin 
    search pmin (p1:ps) | y pmin > y p1 = search p1 ps 
         | y pmin < y p1 = search pmin ps 
         | x pmin > x p1 = search p1 ps 
         | otherwise = search pmin ps 

norm2 :: TwoD -> Float 
norm2 (TwoD x y) = sqrt (x ** 2 + y ** 2) 

minusCosAngleWithX :: TwoD -> Float 
minusCosAngleWithX v = (-1) * dotProduct (TwoD 1 0) v/norm2 v 

-- compare according to the angle with X axis. I did not know about Data.Ord.comparing 
angleWithXCompare :: TwoD -> TwoD -> Ordering 
angleWithXCompare p1 p2 | minusCosAngleWithX p1 > minusCosAngleWithX p2 = GT 
         | minusCosAngleWithX p1 < minusCosAngleWithX p2 = LT 
         | norm2 p1 > norm2 p2 = GT -- break ties 
         | norm2 p1 < norm2 p2 = LT 
         | otherwise = EQ 

vectorDiff :: TwoD -> TwoD -> TwoD 
vectorDiff p1 p2 = TwoD (x p2 - x p1) (y p2 - y p1) 

grahamSort :: [TwoD] -> [TwoD] 
-- sortBy angle (~-cosine) of (p1, p) with x axis 
grahamSort ps = let p1 = grahamGetFirstCandidate ps in 
        p1 : List.sortBy (angleWithXCompare . vectorDiff p1) (filter (/=p1) ps) 
main :: IO() 
main = let ps = [TwoD 4 3, TwoD 5 1, TwoD 4 1, TwoD 1 2, TwoD 5 2, TwoD 2 1, TwoD 3 5, TwoD 2 3] 
    in do 
    print ps 
    print $ grahamGetFirstCandidate ps 
    print $ grahamSort ps 

Вот результат я получаю

[TwoD {x = 4.0, y = 3.0},TwoD {x = 5.0, y = 1.0},TwoD {x = 4.0, y = 1.0},TwoD {x = 1.0, y = 2.0},TwoD {x = 5.0, y = 2.0},TwoD {x = 2.0, y = 1.0},TwoD {x = 3.0, y = 5.0},TwoD {x = 2.0, y = 3.0}] 
TwoD {x = 2.0, y = 1.0} -- This is the correct result 
[TwoD {x = 2.0, y = 1.0},TwoD {x = 5.0, y = 1.0},TwoD {x = 4.0, y = 1.0},TwoD {x = 5.0, y = 2.0},TwoD {x = 4.0, y = 3.0},TwoD {x = 2.0, y = 3.0},TwoD {x = 3.0, y = 5.0},TwoD {x = 1.0, y = 2.0}] 

То, что я хочу (и ожидал), что точка (4, 1) появляется до (5, 1) в отсортированном списке.

Если изменить порядок точек входа она меняет местами (4, 1) и (5, 1) на выходе, а также:

main = let ps = [TwoD 4 3, TwoD 4 1, TwoD 5 1, TwoD 1 2, TwoD 5 2, TwoD 2 1, TwoD 3 5, TwoD 2 3] 
    in do 
    print ps 
    print $ grahamGetFirstCandidate ps 
    print $ grahamSort ps 

[TwoD {x = 4.0, y = 3.0},TwoD {x = 4.0, y = 1.0},TwoD {x = 5.0, y = 1.0},TwoD {x = 1.0, y = 2.0},TwoD {x = 5.0, y = 2.0},TwoD {x = 2.0, y = 1.0},TwoD {x = 3.0, y = 5.0},TwoD {x = 2.0, y = 3.0}] 
TwoD {x = 2.0, y = 1.0} 
[TwoD {x = 2.0, y = 1.0},TwoD {x = 4.0, y = 1.0},TwoD {x = 5.0, y = 1.0},TwoD {x = 5.0, y = 2.0},TwoD {x = 4.0, y = 3.0},TwoD {x = 2.0, y = 3.0},TwoD {x = 3.0, y = 5.0},TwoD {x = 1.0, y = 2.0}] 

Очевидно, я что-то отсутствует, любая помощь будет оценили.

Редактировать: Ну, теперь я замечаю, что порядок последних пунктов неверен: (3, 5) должен появиться перед (2, 3). Когда я печатаю косинусы, они выглядят правильно (= должен давать правильный порядок, вплоть до связей), поэтому, возможно, что-то не так с angleWithXCompare.

Answer 1

Что-то не так с вашей функцией "сравнения", например:

test = 
    let p1 = TwoD {x = 2.0, y = 1.0} 
     p2 = TwoD 5 1 
     p3 = TwoD 4 1 
     cmp = angleWithXCompare . vectorDiff p1 
    in (cmp p2 p3, cmp p3 p2) 

Это дает:

ghci> test 
(LT, LT) 

Я бы ожидать либо (LT,GT) или (GT,LT)

Update: Вы хотите используйте эту функцию сравнения:

cmp a b = angleWithXCompare (vectorDiff p1 a) (vectorDiff p1 b) 

в вашем List.sortBy вызова, например:

grahamSort ps = 
let p1 = grahamGetFirstCandidate ps 
in 
    p1 : List.sortBy cmp (filter (/=p1) ps) 
where cmp a b = angleWithXCompare (vectorDiff p1 a) (vectorDiff p1 b)