Список групп по соотношению эквивалентности

У меня есть отношение эквивалентности R в наборе A. Как я могу построить классы эквивалентности на A? Это что-то вроде groupBy do, но между всеми элементами не только соседи.

Например, 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)]]

Ответ 1

Если вы можете определить совместимое отношение упорядочения, вы можете использовать

equivalenceClasses equal comp = groupBy equal . sortBy comp

что даст вам сложность O(n*log n). Без этого я не вижу никакого способа получить лучшую сложность, чем O(n^2), в основном

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

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

Ответ 2

Для корректной структуры данных используется disjoint set (Tarjan). Чисто функциональная, постоянная реализация такой структуры описывалась Conchon and Filliâtre. В Hackage реализована реализация .

Ответ 3

Здесь небольшое изменение предложения Дэниела:

Так как классы эквивалентности разбивают набор значений (что означает, что каждое значение принадлежит точно одному классу), вы можете использовать значение для представления его класса. Во многих случаях, однако, вполне естественно выбрать одного канонического представителя в классе. В вашем примере вы можете пойти для (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)

Предложение Дэниела является обобщением этого подхода. Я по существу предлагаю конкретное отношение упорядочения (а именно сравнение по представителю), которое может быть легко получено во многих случаях использования.

Предостережение 1: Вы должны убедиться, что представители тех же/разных классов эквивалентности на самом деле равны/различны в соответствии с (==) и compare. Если эти две функции проверяют структурное равенство, это всегда так.

Предостережение 2: Технически вы можете уменьшить тип equivalenceClasses до

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

Ответ 4

Это следующее решение работает немного быстрее, чем Даниэль Фишер на небольших данных (когда время выполнения составляет несколько секунд). Он работает путем добавления элементов в классы эквивалентности один за другим, создавая новый класс, если элемент не принадлежит ни одному из существующих.

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 ([email protected] (x: _): xss) y | x 'eq' y  = (y: xs): xss
                          | otherwise = xs: f xss y

Ответ 5

Другие отметили, что проблему трудно решить эффективно без какой-либо дополнительной структуры отношения эквивалентности. Если вспомнить определения из математики, отношение эквивалентности эквивалентно факторному отображению (то есть функции из вашего набора в классы эквивалентности). Мы можем написать функцию Хаскеля, которая, учитывая фактор-отображение (или, скорее, что-то изоморфное ему) и некоторые хорошие свойства его кодомена, группирует по отношению эквивалентности. Мы также можем определить эквивалентность на основе фактор-карт.

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