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