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