haskell - 从 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

如果您的对组件的类型在 classOrd中，您可以在 O(n log 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)]