Get duplicated elements in a list without using (Ord a)-CodePudding

I have been trying to make a function that concatenates a list of lists, sorts it, and gives back the duplicated values.

The issue I'm facing is that it tells me to change (Eq a) to (Ord a) for the last function, but I cannot do this. How can I solve this without changing (Eq a) to (Ord a) ?

This is the code I have:

group                   :: Eq a => [a] -> [[a]]
group                   =  groupBy (==)

groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  []           =  []
groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs
uniq :: Eq b => [b] -> [b]
uniq = map head . group

insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys) | x < y     = x:y:ys
                | otherwise = y:(insert x ys)

isort :: (Eq a, Ord a) => [a] -> [a]
isort [] = []
isort (x:xs) = insert x (isort xs)

kms :: Ord a => [a]
kms xss = uniq (isort (concat xss))

pairwiseIntersections :: (Eq a) => [[a]] -> [a]
pairwiseIntersections xss = kms xss

CodePudding user response：

You cannot sort a list without its elements having some ordering -- meaning that they must be instances of Ord.

You can do other things to deduplicate a list, like nub, but if you want it sorted you need Ord or an equivalent ordering.

CodePudding user response：

You mention no complexity requirements, so the simplest approach could be

keepOnlyDups [] = []
keepOnlyDups (x:xs) = [x | elem x xs]    keepOnlyDups [ y | y <- xs, y /= x]

removeExtras [] = []
removeExtras (x:xs) = [x]    removeExtras [ y | y <- xs, y /= x]

answering both your question's text and the implied meaning of the code.

Implementing keepOnlyUniques is left as an exercise, if you're interested in that.