按等价关系列出的组列表

Question

我在集合上有等价关系 .如何构建等价类？它就是这样,但在所有元素之间,不仅仅是邻居.RAAgroupBy

例如,equal是等价关系(它是自反,对称和传递二元关系):

type Sometuple = (Int, Int, Int)

equal :: Sometuple -> Sometuple -> Bool
equal (_, x, _) (_, y, _) = x == y

它实际上是连接2个Sometuple元素的谓词.

?> equal (1,2,3) (1,2,2)
True

那么,我如何[Sometuple]基于equal谓词构建所有等价类？像这样的东西:

equivalenceClasses :: (Sometuple -> Sometuple -> Bool) -> [Sometuple] -> [[Sometuple]]
?> equivalenceClasses equal [(1,2,3), (2,1,4), (0,3,2), (9,2,1), (5,3,1), (1,3,1)]
[[(1,2,3),(9,2,1)],[(2,1,4)],[(0,3,2),(5,3,1),(1,3,2)]]

Answer 1

如果您可以定义兼容的订购关系,则可以使用

equivalenceClasses equal comp = groupBy equal . sortBy comp

哪会给你O(n*log n)复杂性.没有它O(n^2),基本上我没有看到任何方法来获得更好的复杂性

splitOffFirstGroup :: (a -> a -> Bool) -> [a] -> ([a],[a])
splitOffFirstGroup equal xs@(x:_) = partition (equal x) xs
splitOffFirstGroup _     []       = ([],[])

equivalenceClasses _     [] = []
equivalenceClasses equal xs = let (fg,rst) = splitOffFirstGroup equal xs
                              in fg : equivalenceClasses equal rst