Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: removing duplicate tuples (including symmetrical ones)
(edgar klerks)
2. Re: removing duplicate tuples (including symmetrical ones)
(Ozgur Akgun)
3. step by step binding recursion (Nehemiah Clark)
4. Re: removing duplicate tuples (including symmetrical ones)
(Martin Tomko)
5. Re: removing duplicate tuples (including symmetrical ones)
(Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Tue, 28 Sep 2010 12:01:54 +0200
From: edgar klerks <[email protected]>
Subject: Re: [Haskell-beginners] removing duplicate tuples (including
symmetrical ones)
To: [email protected]
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
You made the same mistake :)
removeDuplTuples x:xs = nub(if ((snd x,fst x) `elem` xs) then
(removeDuplTuples xs) else ([x] ++ removeDuplTuples xs))
Should be:
removeDuplTuples (x:xs) = nub(if ((snd x,fst x) `elem` xs) then
(removeDuplTuples xs) else ([x] ++ removeDuplTuples xs))
You need to put parenthesis around x:xs.
Greets,
Edgar
On Tue, Sep 28, 2010 at 11:57 AM, Martin Tomko <[email protected]>wrote:
> Hi Edgar,
> thanks for the help. I wanted to first test with nub, but I still cannot
> get it to work. I cannot see any missing parenthesis, but I retyped it this
> way to check:
>
>
> removeDuplTuples :: (Eq a) =>[(a,a)] -> [(a,a)]
> removeDuplTuples [] = []
> removeDuplTuples [b] = [b]
> removeDuplTuples x:xs = nub(if ((snd x,fst x) `elem` xs) then
> (removeDuplTuples xs) else ([x] ++ removeDuplTuples xs))
>
> still the same error
>
> What am I missing?
> Martin
>
>
> On 9/28/2010 11:45 AM, edgar klerks wrote:
>
> >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.
>
> type has to be typo.
> On Tue, Sep 28, 2010 at 11:44 AM, edgar klerks <[email protected]>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, 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]
>>
>> But I haven't test it thoroughly.
>>
>> Greets,
>>
>> Edgar
>>
>> On Tue, Sep 28, 2010 at 11:33 AM, Martin Tomko
>> <[email protected]>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
>>> _______________________________________________
>>> Beginners mailing list
>>> [email protected]
>>> http://www.haskell.org/mailman/listinfo/beginners
>>>
>>
>>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20100928/ab3c94d3/attachment-0001.html
------------------------------
Message: 2
Date: Tue, 28 Sep 2010 11:05:14 +0100
From: Ozgur Akgun <[email protected]>
Subject: Re: [Haskell-beginners] removing duplicate tuples (including
symmetrical ones)
To: [email protected]
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="utf-8"
Hi,
On 28 September 2010 10:33, Martin Tomko <[email protected]> wrote:
> I have a list of (a,a) tuples, and am trying something like nub, but also
> matching for symmetrical tuples.
You can of course do this. One approach would be to simply 'fix' the tuples
according to some ordering, and then use standard nub - or a better one.
But to me, the real question is this: If the order of your tuples to don't
matter, do you actually need tuples? There are other types in which the
order of the elements in a container does not change the meaning; such as a
set. You may want to use a Set from Data.Set, or you can define a pair type
in which ordering doesn't matter. It will end up being a cardinality
restricted set type though.
If you just want to get it working, here is some code for the first option:
nubSym :: Ord a => [(a,a)] -> [(a,a)]
nubSym = nub . map fix
where fix (a,b) | a > b = (b,a)
fix p = p
Cheers,
Ozgur
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20100928/7b544554/attachment-0001.html
------------------------------
Message: 3
Date: Tue, 28 Sep 2010 03:13:08 -0700 (PDT)
From: Nehemiah Clark <[email protected]>
Subject: [Haskell-beginners] step by step binding recursion
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
Hi,
If anyone is familar with Prolog, then you might have used the "trace" or
"gtrace" function. I was wondering which function can I use to show the
bindings in the recursion. It would be helpful for me to see what is going.
Thanks
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20100928/327edbe5/attachment-0001.html
------------------------------
Message: 4
Date: Tue, 28 Sep 2010 12:14:27 +0200
From: Martin Tomko <[email protected]>
Subject: Re: [Haskell-beginners] removing duplicate tuples (including
symmetrical ones)
To: Ozgur Akgun <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
Hi Ozgur,
well, I am getting a list of tuples from a previous function, and they
relate to edges in graphs, so I am not too keen to change that, although
that could be possible. But I never worked with sets in Haskell, so will
have to study.
Regarding your suggestion - I have to study it, it is a bit advanced.
First, I see there is no paramter to nubSym - I have never used that
syntax, shouldn't there be something like nymSym (x:xs) or so?
Second, obviously there is a local function, fix. I understand this: fix
(a,b) | a > b = (b,a)
but I am not sure how to interpret this:
fix p = p. Where does p come from? How does haskell know that it relates
to (a,b), or the x as parameter?
Just asking for clarification ,as I am new to all this.
Thanks
M.
On 9/28/2010 12:05 PM, Ozgur Akgun wrote:
> Hi,
>
> On 28 September 2010 10:33, Martin Tomko <[email protected]
> <mailto:[email protected]>> wrote:
>
> I have a list of (a,a) tuples, and am trying something like nub,
> but also matching for symmetrical tuples.
>
>
> You can of course do this. One approach would be to simply 'fix' the
> tuples according to some ordering, and then use standard nub - or a
> better one.
>
> But to me, the real question is this: If the order of your tuples to
> don't matter, do you actually need tuples? There are other types in
> which the order of the elements in a container does not change the
> meaning; such as a set. You may want to use a Set from Data.Set, or
> you can define a pair type in which ordering doesn't matter. It will
> end up being a cardinality restricted set type though.
>
> If you just want to get it working, here is some code for the first
> option:
>
> nubSym :: Ord a => [(a,a)] -> [(a,a)]
> nubSym = nub . map fix
> where fix (a,b) | a > b = (b,a)
> fix p = p
>
> Cheers,
> Ozgur
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20100928/309f6c17/attachment-0001.html
------------------------------
Message: 5
Date: Tue, 28 Sep 2010 12:21:39 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] removing duplicate tuples (including
symmetrical ones)
To: [email protected]
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
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
<[email protected]>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
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 27, Issue 59
*****************************************
