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

Question

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

14

我有一个关于集合A的等价关系R。如何在A上构建等价类？这有点像groupBy，但是不仅限于相邻元素。

例如，equal是一种等价关系（它是自反、对称和传递二元关系）：

type Sometuple = (Int, Int, Int)

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

它实际上是一个谓词，用于连接两个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)]]

- ДМИТРИЙ МАЛИКОВ

你可能会发现这个包很有用。http://hackage.haskell.org/package/equivalence - yihuang

equivalence 包需要一些可变的单子上下文 (IO 或 ST)。尝试使用 persistent-equivalence 代替，它更加简洁。 - mergeconflict

6个回答

3

这里使用的正确数据结构是不相交集合（Tarjan）。Conchon和Filliâtre描述了这种结构的纯函数、持久化实现。在Hackage上有一个实现。

- mergeconflict

1

你能解释一下如何使用不相交集合结构来获得比丹尼尔·费舍尔更好的算法吗？我不明白。 - Max

1

这是对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]]

- Jannis Limperg

1

其他人注意到，如果在等价关系上没有额外的结构，那么解决这个问题是很难高效地完成的。如果回想数学中的定义，等价关系等价于商映射（即从您的集合到等价类的函数）。我们可以编写一个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) [...]

- Dan Robertson

0

以下解决方案在小数据上的执行速度比Daniel Fischer的要快一些（列表长度小于约2¹⁴ = 16384个元素）。它通过逐个将元素添加到等价类中，如果一个元素不属于任何现有的等价类，则创建一个新的等价类。

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

- Ignat Insarov

0

原来在GHC.Exts中也有类似的函数。

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

这需要您定义一个函数，将您的类型映射到具有兼容Ord且Eq与您的等价概念相符的类型。(这里是snd。)范畴上，您可以将此函数视为箭头，指向等价类的集合，也称为商映射。

感谢Olaf指出。

- Ignat Insarov

一些基本的例子可以帮助澄清“箭头”的含义。 - Will Ness

@WillNess 嗯，snd呢？ - Ignat Insarov

啊，好的。______________ - Will Ness

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Fischer · Accepted Answer

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

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