[Haskell-beginners] removing duplicate tuples (including symmetrical ones)

Daniel Fischer daniel.is.fischer at web.de
Tue Sep 28 06:21:39 EDT 2010


On Tuesday 28 September 2010 11:44:41, edgar klerks wrote:
> Hi Martin,
>
> You have some typos:
>
> import Data.List
> removeDuplTuples :: (Eq a) => [(a,a)] -> [(a,a)]
> removeDuplTuples [] = []
> removeDuplTuples [b] =
> [b]
> -- using the syntactic sugar for single element in list
> removeDuplTuples (x:xs) = nub (if elem (snd x,fst x) xs then
> removeDuplTuples xs else [x] ++ removeDuplTuples xs)
>                              --------
> You forgot the parenthesis. Parse error in pattern usually means a type
> in the input of one of your functions. Nub needs elements that can be
> equal.
>
> Nub is quitte inefficient,

Yes, it's O(n^2), but at its type (requiring only equality,no ordering), no 
more efficient solution is known [perhaps it can even be proved that O(n^2) 
is the best you can achieve].
If you have an Ord instance, it can be done in O(n*log n), so if you can 
assume that, it's better to not use nub.

> if your elements can be ordered, there is a
> more efficient version. It is something like:
>
> fmap head.group.sort $ [1,1,1,1,4,4,5,6,6,7,8,9]
> [1,4,5,6,7,8,9]

Yes, that's a typical idiom.
It doesn't quite solve the problem at hand, because Martin also wants to 
remove one of [(1,2),(2,1)].

If no Ord instance is available,

symEq :: Eq a => (a,a) -> (a,a) -> Bool
symEq (x,y) (u,v) = (x == u && y == v) || (x == v && y == u)
-- parentheses not necessary

removeDuplTuples :: Eq a => [(a,a)] -> [(a,a)]
removeDuplTuples = nubBy symEq

If Ord is available, you can for example write a comparison function 
symComp and use

removeDuplTuples :: Ord a => [(a,a)] -> [(a,a)]
removeDuplTuples = map head . groupBy symEq . sortBy symComp

Or you map the tuples to a normalized representation first

normalize t@(x,y)
    | y < x    = (y,x)
    | otherwise = t

and have

removeDuplTuples = map head . group . sort . map normalize

or you can decorate-sort-undecorate, or ...

>
> But I haven't test it thoroughly.
>
> Greets,
>
> Edgar
>
> On Tue, Sep 28, 2010 at 11:33 AM, Martin Tomko 
<martin.tomko at geo.uzh.ch>wrote:
> > Hi all,
> > I apologize for spamming this forum so frequently, but there is noone
> > I can turn to around here...
> > I have a list of (a,a) tuples, and am trying something like nub, but
> > also matching for symmetrical tuples. I implemented it using the
> > template from delete from Prelude. Seems like my typse signature has
> > some troubles (Paarse error in pattern) but I am not sure where the
> > problem is.
> >
> > removeDuplTuples :: [(a,a)] -> [(a,a)]
> > removeDuplTuples [] = []
> > removeDuplTuples [b] = [b]
> >
> >         -- using the syntactic sugar for single element in list
> > removeDuplTuples x:xs = nub (if elem (snd x,fst x) xs then
> > removeDuplTuples xs else [x] ++ removeDuplTuples xs)
> >
> > I assume the problem lies in elem (snd x,fst x) xs but I am not sure
> > how to rewrite it.
> >
> > Thanks for all help,
> > Martin



More information about the Beginners mailing list