从Haskell中的元组列表中返回唯一的元组 [英] Return unique tuples from a list of tuples in Haskell

问题描述

（A，B），（B，A），（D，C），（E，F），（C，D），（ F，E）] 。如何返回 [（A，B），（C，D），（E，F）] 的列表？我发现的唯一解决方案是去除重复的元组，我能想到的唯一解决方案是天真的O（n ^ 2）解决方案。有没有办法有效地做到这一点？

解决方案

如果对的组件类型在类 Ord ，你可以在O（n log n）时间内完成它：

  import Data.List（排序，组）
 
 sortPair :: Ord a => （a，a） - > （a，a）
 sortPair（x，y）
 | x <= y =（x，y）
 |否则=（y，x）
 
 uniques :: Ord a => [（a，a）]  - > [（a，a）] 
 uniques =地图头。组。排序。 map sortPair 
  

所以，如果我们定义

  data T = A | B | C | D | E | F派生（Eq，Ord，Show）
  

我们有，例如：

 > （A，B），（B，A），（D，C），（E，F），（C，D），（F，E）] 
 [（A，B）， C，D），（E，F）] 
  

I have a list of tuples of the form [(A,B),(B,A),(D,C),(E,F),(C,D),(F,E)]. How do I return a list that is just [(A,B),(C,D),(E,F)]? The only solutions I've found are to remove repeated tuples, and the only solutions I can think of are the naive O(n^2) solutions. Is there a way to do this efficiently?

解决方案

If the type of the components of your pairs is in the class Ord, you can do it in O(n log n) time:

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

So, if we define

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

we have, for your example:

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

这篇关于从Haskell中的元组列表中返回唯一的元组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！