[Haskell-beginners] removing duplicate tuples (including
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] =
> -- 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
> 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]
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
| y < x = (y,x)
| otherwise = t
removeDuplTuples = map head . group . sort . map normalize
or you can decorate-sort-undecorate, or ...
> But I haven't test it thoroughly.
> 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