Возвратите уникальные кортежи из списка кортежей в Haskell

Question

У меня есть список кортежей формы [(A,B),(B,A),(D,C),(E,F),(C,D),(F,E)]. Как мне вернуть список, который равен [(A,B),(C,D),(E,F)]? Единственные решения, которые я нашел, - удалить повторяющиеся кортежи, и единственными решениями, которые я могу себе представить, являются наивные решения O (n^2). Есть ли способ сделать это эффективно?

Answer 1

Если тип компонентов ваших пар в классе Ord, вы можете сделать это в O (N журнал N) Время:

import Data.List (sort, group) 

sortPair  :: Ord a => (a, a) -> (a, a) 
sortPair (x, y) 
    | x <= y  = (x, y) 
    | otherwise = (y, x) 

uniques :: Ord a => [(a, a)] -> [(a, a)] 
uniques = map head . group . sort . map sortPair 

Таким образом, если мы определим

data T = A | B | C | D | E | F deriving (Eq, Ord, Show) 

у нас есть, для примера:

> uniques [(A,B),(B,A),(D,C),(E,F),(C,D),(F,E)] 
[(A,B),(C,D),(E,F)]