CODEWITHSUNDEEP
haskellgrouping
nipuL
nipuL

Reputation: 11

Grouping duplicates

Haskell gurus. Care to show me some more haskellian ways to perform this task that isn't restricted by my limited knowledge of haskell and FP in general?

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

Upvotes: 1

Views: 482

Answers (4)

pat
pat

Reputation: 12749

This function requires only 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)

Upvotes: 0

Ankur
Ankur

Reputation: 33637

Here is something weird to do this.

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

Upvotes: 0

Jonas Dureg&#229;rd
Jonas Dureg&#229;rd

Reputation: 937

If you want to avoid introducing an Ord constraint in the type you can use this:

import Data.List

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

It's correspondingly slower than (group . sort) and groups are ordered by first occurrence in the original list:

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

You might be able to improve complexity slightly by making a helper function that accumulates into a parameter list, ask if you're interested in the details.

Upvotes: 1

li.davidm
li.davidm

Reputation: 12116

You could sort the list, then group it:

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

Upvotes: 4

Related Questions