Блог

Главная - Вопросы по программированию - Группировка дубликатов

Группировка дубликатов

#haskell #grouping

#haskell #группировка

Вопрос:

Гуру Haskell. Не могли бы вы показать мне еще несколько хаскелевских способов выполнения этой задачи, которые не ограничены моими ограниченными знаниями о haskell и FP в целом?

 groupDups [] = []
groupDups list@(x:xs) = groupDups' x list
  where groupDups' _ [] = []
        groupDups' x list = let (m,r) = partition (x ==) list
                            in m : groupDups r

> groupDups [1,2,3,4,1,2,3,4,4,3,2,1,4,3,2,1]
[[1,1,1,1],[2,2,2,2],[3,3,3,3],[4,4,4,4]]

Ответ №1:

Вы могли sort бы список, затем group он:

 > import Data.List
> (group . sort) [1,2,3,4,1,2,3,4,4,3,2,1,4,3,2,1]
[[1,1,1,1],[2,2,2,2],[3,3,3,3],[4,4,4,4]]

Комментарии:

1. Приветствия, это намного быстрее, похоже, я снова все обдумал. Однако теперь мне нужно реализовать экземпляр Ord для моего пользовательского типа данных.

2. @nipuL, это, или вы могли бы использовать sortBy вместо сортировки. Тогда вам просто понадобится Eq group .

3. sortBy все еще нужна функция, которая возвращает Ordering заданные два ключа.

4. @nipuL: вы не можете просто derive это сделать?

Ответ №2:

Если вы хотите избежать введения Ord ограничения в тип, вы можете использовать это:

 import Data.List

groupDups []     = []
groupDups (x:xs) = (x : group) : groupDups xs' where
  (group,xs') = partition (==x) xs

Это соответственно медленнее, чем (group . sort) и группы упорядочены по первому вхождению в исходном списке:

 *Main> groupDups [1,3,2,3,4,1,2,3,4,4,3,2,1,4,3,2,1]
[[1,1,1,1],[3,3,3,3,3],[2,2,2,2],[4,4,4,4]]

Возможно, вы сможете немного повысить сложность, создав вспомогательную функцию, которая накапливается в списке параметров, спросите, заинтересованы ли вы в деталях.

Ответ №3:

Вот что-то странное для этого.

 groupDups ls = 
   map ((h:­t) -> t) $ foldl­ (s e -> map ((h:­t) -> if h == e then (e:h:­t) else (h:t)­) s)   (nub [[x] | x <- ls])­ ls

Ответ №4:

Эта функция требует только Eq 

 groupDups xs = foldl insert [] xs
  where insert [] x = [[x]]
        insert (ys@(y:_):yss) x | x == y    = (x:ys):yss
                                | otherwise = ys:(insert yss x)