haskell - 如何合并 Haskell 中的所有相交(Set a)？

Question

我有一组由 Data.Set 中的 Set (Set a) 类型表示的集合.

我想联合所有交集不为空的成员集。

同样，如果 x 和 y 在同一个 Set 中。

示例:

-- import qualified Data.Set as S
ghci> f $ S.fromList [S.fromList [1,2], S.fromList [2,3], S.fromList [5]]
> S.fromList [S.fromList [1,2,3], S.fromList [5]]

ghci> f $ S.fromList [ S.fromList [1,2], S.fromList [2,3], S.fromList [3,4] ]
> S.fromlist [ S.fromList [1,2,3,4] ]

什么是优雅且性能的解决方案？

Answer 1

对于要合并的大量集合，您要使用 union find算法。

您可以在此处找到实现联合查找算法的 Haskell 代码:

https://github.com/erantapaa/union-find-example

此外，对于 Int 集，您需要使用 Data.IntSet - 它效率更高。

之前我写了以下不传递合并集合的内容:

这是一个折叠:

import qualified Data.Set as S
import Data.List (foldl')

mergeSets as = foldl' merge [] as

-- merge one set into a list of sets
merge [] a = [a]
merge (b:bs) a = if S.null (S.intersection a b)
                    then b : merge bs a
                    else (S.union a b) : bs

test = mergeSets [ S.fromList [1,2], S.fromList [2,3], S.fromList [5] ]