如何高效去除Haskell中Data.Sequence的重复元素？

你当前的fromList $ nub $ toList mysequence方案确实能用，但时间复杂度是O(n²)——nub会逐个检查每个元素是否已经在前面的子列表中，每次检查都要遍历已有的元素做Eq比较，当序列规模变大时，性能会急剧下降。

针对你的Edge类型（无序边，Edge i j和Edge j i视为相等），可以通过以下两种更高效的方式实现去重：

核心思路：规范化Edge + 哈希/有序集合跟踪 #

因为你的Eq实例是基于“无序边”的，所以首先要把每个Edge转换成规范化形式（比如让两个Int按从小到大排列），这样不管原始顺序如何，相等的Edge都会被转换成同一个值。之后用哈希集合（HashSet）或有序集合（Set）来跟踪已经出现过的Edge，这两种结构的查找操作复杂度远低于线性遍历。

第一步：实现Edge的规范化函数 #

先写一个辅助函数，把任意Edge转换成有序形式：

normalizeEdge :: Edge -> Edge
normalizeEdge (Edge i j) = Edge (min i j) (max i j)

方案一：用HashSet实现O(n)平均复杂度的去重 #

HashSet的查找和插入操作平均是O(1)，整体复杂度可以降到O(n)，适合大规模序列。

1. 给Edge添加Hashable实例 #

要使用HashSet，需要让Edge的哈希值和Eq逻辑一致（相等的Edge哈希值必须相同）：

import Data.Hashable

instance Hashable Edge where
  hashWithSalt salt (Edge i j) = hashWithSalt salt (min i j, max i j)

2. 实现高效去重函数 #

遍历一次Seq，用HashSet记录已经见过的规范化Edge，只保留首次出现的原始Edge：

import qualified Data.Sequence as Seq
import qualified Data.HashSet as HS
import Data.Foldable (foldl')

nubSeq :: Seq Edge -> Seq Edge
nubSeq = Seq.fromList . reverse . fst . foldl' go ([], HS.empty)
  where
    go (acc, seen) edge =
      let norm = normalizeEdge edge
      in if HS.member norm seen
         then (acc, seen)
         else (edge : acc, HS.insert norm seen)

方案二：用Set实现O(n log n)复杂度的去重 #

如果不想引入Hashable依赖，可以用Set，它基于Ord实例，查找和插入是O(log n)，整体复杂度O(n log n)，比HashSet稍慢但足够高效。

1. 给Edge添加Ord实例 #

让Ord实例和Eq逻辑一致，相等的Edge比较结果为EQ：

instance Ord Edge where
  compare (Edge i j) (Edge i' j') = compare (min i j, max i j) (min i' j', max i' j')

2. 实现去重函数 #

逻辑和HashSet版本类似，只是替换成Set：

import qualified Data.Sequence as Seq
import qualified Data.Set as Set
import Data.Foldable (foldl')

nubSeq :: Seq Edge -> Seq Edge
nubSeq = Seq.fromList . reverse . fst . foldl' go ([], Set.empty)
  where
    go (acc, seen) edge =
      let norm = normalizeEdge edge
      in if Set.member norm seen
         then (acc, seen)
         else (edge : acc, Set.insert norm seen)

为什么不能用nubBy？ #

nubBy (==)和原生nub本质一样，都是O(n²)复杂度，只是允许自定义比较函数，但并没有解决线性遍历检查的性能问题，所以不推荐。

内容的提问来源于stack exchange，提问作者Stéphane Laurent