Eliminating the duplicates completely in Haskell

Question

I have this code but it does not do what I want totally, I takes a list of tuples;

[(3,2),(1,2),(1,3),(1,2),(4,3),(3,2),(1,2)]

and gives

[(1,3),(4,3),(3,2),(1,2)]

but I want it to give

[(1,3),(4,3)]

where am I doing wrong? Thanks in advance.

eliminate :: [(Int,Int)] -> [(Int,Int)]
eliminate [] = []
eliminate (x:xs)
    | isTheSame xs x  = eliminate xs
    | otherwise       = x : eliminate xs


isTheSame :: [(Int,Int)] -> (Int,Int) -> Bool
isTheSame [] _ = False
isTheSame (x:xs) a
    | (fst x) == (fst a) && (snd x) == (snd a)  = True
    | otherwise                 = isTheSame xs a

What do you mean with "totally", why exactly should `(3,2)` and `(1,2)` be excluded? — Landei, Apr 02 '13 at 18:50
I am searchin for a function that eliminates the duplicates completely, only the unique ones should be there, I guess I should change my implementation :/ — Karavana, Apr 02 '13 at 18:55

Niklas B. · Accepted Answer · 2013-04-02T19:02:11.527

7

The code is almost correct. Just change this line

    | isTheSame xs x  = eliminate xs

to

    | isTheSame xs x  = eliminate $ filter (/=x) xs

The reason is that if x is contained in xs, you want to delete all occurences of x.

That said, there are a few parts in your code sample that could be expressed more elegantly:

(fst x) == (fst a) && (snd x) == (snd a) is the same as x == a
isTheSame is the same as elem, only with its arguments reversed

Thus, we could express the function eliminate like this:

eliminate [] = []
eliminate (x:xs)
  | x `elem` xs = eliminate $ filter (/=x) xs
  | otherwise = x : eliminate xs

edited Apr 02 '13 at 19:02

answered Apr 02 '13 at 18:56

Niklas B.

92,950
18
194
224

ow yes! I was filtering that part to exclude x from the xs part but I was not able to manage it thank you :) – Karavana Apr 02 '13 at 18:59
2

@Karavana: Check my edit, you should use `elem` instead of your custom, highly specialized `isTheSame` function (which also has a strange name) – Niklas B. Apr 02 '13 at 19:01
I was just about to suggest that change. – Daniel Fischer Apr 02 '13 at 19:02
[This one](http://stackoverflow.com/revisions/15772150/2), you have just missed the grace period ;) – Daniel Fischer Apr 02 '13 at 19:04
when I add filter part it gives "Instance of Eq [(Int,Int)] required for eliminate " error, what may cause this? – Karavana Apr 02 '13 at 19:20
@Karavana That makes no sense. The code requires an `Eq` instance for `(Int,Int)`, but not for `[(Int,Int)]`. However, there is an `Eq` instance for both, `(Int,Int)` and `[(Int,Int)]`. Besides, that error message doesn't read like one from either ghc(i) or - if memory serves - from hugs. What implementation are you using? – Daniel Fischer Apr 02 '13 at 19:28
I am using hugs, also I should say that my original code doesnot consist of homogeneous [(Int,Int)] type, but I am comparing just this two int values from [(Int,Int,Char,Char)] like model. I guess that is causing the error maybe? – Karavana Apr 02 '13 at 19:31
@Karavana Tuples with more than 7 components? Then you need to write an instance (would work in ghci for tuples up to 15). Or, wait, you say you only use the two `Int`s as the criterion, so replace `elem` with a function `elemBy`. – Daniel Fischer Apr 02 '13 at 19:33
exactly :( Unnfortunately I don't know how to do that. Well :/ – Karavana Apr 02 '13 at 19:36
@Karavana You define `consideredEqual :: -> Tuple -> Tuple -> Bool`. Then use that in `any consideredEqual list` (so `elemBy` would just be `any`, surprisingly I managed to type faster than I could think). – Daniel Fischer Apr 02 '13 at 19:39
I got it worked at last :D with pattern matching, like you said I've created a function to get it filtered. – Karavana Apr 02 '13 at 22:04

score 5 · Answer 2 · edited May 23 '17 at 12:13

5

This should do it:

-- all possibilities of picking one elt from a domain
pick :: [a] -> [([a], a)]
pick []     = [] 
pick (x:xs) = (xs,x) : [ (x:dom,y) | (dom,y) <- pick xs]

unique xs = [x | (xs,x) <- pick xs, not (elem x xs)]

Testing:

*Main Data.List> unique [(3,2),(1,2),(1,3),(1,2),(4,3),(3,2),(1,2)]
[(1,3),(4,3)]

More here and in Splitting list into a list of possible tuples

Following Landei's lead, here's a short version (although it'll return its results sorted):

import Data.List

unique xs = [x | [x] <- group . sort $ xs]

edited May 23 '17 at 12:13

Community

1
1

answered Apr 02 '13 at 18:56

Will Ness

70,110
9
98
181

good implementation Will, I appreciate your effort but I am interested in whats wrong with my implementation, but yours is perfect tho :) – Karavana Apr 02 '13 at 19:00

score 4 · Answer 3 · answered Apr 02 '13 at 19:32

4

Inefficient reference implementation.

import Data.List

dups xs = xs \\ nub xs
eliminate xs = filter (`notElem` dups xs) xs

answered Apr 02 '13 at 19:32

luqui

59,485
12
145
204

Landei · Answer 4 · 2013-04-02T21:53:13.517

3

A shorter version (but results will be sorted):

import Data.List

eliminate :: [(Int,Int)] -> [(Int,Int)]
eliminate = concat . filter ((== 1) . length) . group . sort

Or with Maybe (thank you, Marimuthu):

import Data.List
import Data.Maybe

eliminate = mapMaybe f . group . sort where f [x] = Just x; f _ = Nothing

Thinking about... we could use lists instead of Maybe:

import Data.List

eliminate = (>>= f) . group . sort where  f [x] = [x]; f _ = []

edited Apr 02 '13 at 21:53

answered Apr 02 '13 at 19:06

Landei

54,104
13
100
195

Is there a reason for using join instead of concat? By using concat, the import of Control.Monad is not necessary. – kaan Apr 02 '13 at 19:12
1

```eliminate = mapMaybe f . group . sort where f [x] = Just x; f _ = Nothing``` since ```catMaybes . map f``` is simply ```mapMaybe f``` – Marimuthu Madasamy Apr 02 '13 at 19:46
2

`[x | [x] <- group . sort $ xs]`. :) – Will Ness Apr 02 '13 at 22:13
thanks for the inspiration BTW (for the shorter variant). I've added it to my answer. :) – Will Ness Apr 03 '13 at 03:52

Eliminating the duplicates completely in Haskell

4 Answers4