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

Question

гуру Хаскелла.Не хочешь показать мне еще несколько способов выполнения этой задачи, которые не ограничены моими ограниченными знаниями по 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]]

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

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

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

Answer 3

Для этой функции требуется только 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)

Answer 4

Вот что-то странное, чтобы сделать это.

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