按等价关系对列表进行分组

我在集合A上有一个等价关系R。如何在A上建立等价类?这有点像groupBy，但在所有元素之间，而不仅仅是相邻元素。

例如，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

那么，我如何基于equal谓词在[Sometuple]上构建所有等价类?像这样:

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)]]

如果你可以定义一个兼容的排序关系，你可以使用

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

此处正确的数据结构是不相交集 (Tarjan)。Conchon和filli描述了这种结构的一个纯功能的、持久的实现。在Hackage上有一个实现。

这是Daniel的建议的一个细微变化:

由于等价类划分了一组值(意味着每个值只属于一个类)，因此可以使用一个值来表示它的类。然而，在许多情况下，为每个类选择一个典型代表是很自然的。在您的示例中，您可以使用(0,x,0)来表示类{ (0,0,0), (0,0,1), (1,0,0), (1,0,1), (2,0,0), ... }。因此，您可以定义一个代表性函数，如下所示:

representative :: Sometuple -> Sometuple
representative (_,x,_) = (0,x,0)

现在，根据定义，equal a b与(representative a) == (representative b)是相同的。因此，如果你按代表性排序一个值列表——假设我们处理的是Ord的成员——相同等价类的成员最终彼此相邻，可以通过普通groupBy分组。

你要找的函数变成了:

equivalenceClasses :: Ord a => (a -> a) -> [a] -> [[a]]
equivalenceClasses rep = groupBy ((==) `on` rep) . sortBy (compare `on` rep)

Daniel的建议是对这种方法的概括。我实际上是在提出一种特定的排序关系(即代表的比较)，它可以在许多用例中很容易地推导出来。

警告1:您需要确保相同/不同等价类的代表根据(==)和compare实际上是相等/不同的。如果这两个函数检验结构相等，则总是如此。

警告2:从技术上讲，您可以将equivalenceClasses的类型放宽为

equivalenceClasses :: Ord b => (a -> b) -> [a] -> [[a]]

其他人注意到，如果在等价关系上没有一些额外的结构，这个问题很难有效地解决。如果回忆一下数学中的定义，等价关系等价于商映射(即从你的集合到等价类的函数)。我们可以写一个Haskell函数，给定商映射(或者说是与它同构的东西)和它的上域的一些很好的性质，用等价关系分组。我们也可以基于商映射定义等价。

import Data.Map
group :: Ord b => (a -> b) -> [a] -> [[a]]
group q xs = elems $ fromListWith (++) [(q x, [x]) | x <- xs]
sameClass :: Eq b => (a -> b) -> (a -> a -> Bool)
sameClass q a b = q a == q b
-- for your question
equal = sameClass ((_,x,_) -> x)
group ((_,x,_) -> x) [...]

下面的解决方案在小数据(小于2¹⁴= 16384个元素的列表)上的执行速度比Daniel Fischer的快一点。它的工作原理是将元素一个接一个地添加到等价类中，如果元素不属于任何现有的类，则创建一个新类。

module Classify where
import qualified Data.List as List
classify :: Eq a => [a] -> [[a]]
classify = classifyBy (==)
classifyBy :: (a -> a -> Bool) -> [a] -> [[a]]
classifyBy eq = List.foldl' f [ ]
  where
    f [ ] y = [[y]]
    f (xs@ (x: _): xss) y | x `eq` y  = (y: xs): xss
                          | otherwise = xs: f xss y

原来在GHC.Exts中有一个类似的功能。

λ import GHC.Exts
λ groupWith snd [('a', 1), ('b', 2), ('c', 1)]
[[('a',1),('c',1)],[('b',2)]]

它要求您定义一个函数，从您的类型到具有兼容的类型Ord，其中Eq与你的等价概念一致。(snd here.)当然，你可以把这个函数看作是指向等价类集合的一个箭头，也称为商映射。

感谢Olaf的指出

相关内容

最新更新

热门标签：