repetition

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

repetition

Luca Ciciriello
Hi All.
Is there any function in Prelude that removes the repeated elements in a list?

In example I've a list like this one: xs = ["3","3","3","3","3","4","4","4","4","4","5","5","5","5","5","6","6","6","6","6","6","6"]

I need a function f such that f xs = ["3","4","5","6"]

thanks in advance for any answer.

Luca

Reply | Threaded
Open this post in threaded view
|

repetition

Thomas Davie

On 4 Aug 2011, at 10:31, Luca Ciciriello wrote:

> Hi All.
> Is there any function in Prelude that removes the repeated elements in a list?
>
> In example I've a list like this one: xs = ["3","3","3","3","3","4","4","4","4","4","5","5","5","5","5","6","6","6","6","6","6","6"]
>
> I need a function f such that f xs = ["3","4","5","6"]
>
> thanks in advance for any answer.

map head . group

Bob

Reply | Threaded
Open this post in threaded view
|

repetition

Ozgur Akgun
In reply to this post by Luca Ciciriello
Hi.

On 4 August 2011 10:31, Luca Ciciriello <luca_ciciriello at hotmail.com> wrote:

> Is there any function in Prelude that removes the repeated elements in a
> list?
>

http://haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#v:nub

HTH,
Ozgur
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20110804/20d14237/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

repetition

Lyndon Maydwell
In reply to this post by Thomas Davie
nub

> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>


Reply | Threaded
Open this post in threaded view
|

repetition

Lyndon Maydwell
Ah sorry, nub that requires importing Data.List. My mistake!

On Thu, Aug 4, 2011 at 5:36 PM, Lyndon Maydwell <maydwell at gmail.com> wrote:
> nub
>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>


Reply | Threaded
Open this post in threaded view
|

repetition

Thomas Davie
In reply to this post by Lyndon Maydwell

On 4 Aug 2011, at 10:36, Lyndon Maydwell wrote:

> nub

Heh, our differing answers point out an ambiguity in the question.

Luca, given [5,10,10,5] what is this function expected to produce?

if you want [5,10] then nub is correct.
if you want [5,10,5] then map head . group is correct.

Bob


Reply | Threaded
Open this post in threaded view
|

repetition

Luca Ciciriello
In reply to this post by Thomas Davie
Thanks.

Luca.

On Aug 4, 2011, at 11:33 AM, Thomas Davie wrote:

>
> On 4 Aug 2011, at 10:31, Luca Ciciriello wrote:
>
>> Hi All.
>> Is there any function in Prelude that removes the repeated elements in a list?
>>
>> In example I've a list like this one: xs = ["3","3","3","3","3","4","4","4","4","4","5","5","5","5","5","6","6","6","6","6","6","6"]
>>
>> I need a function f such that f xs = ["3","4","5","6"]
>>
>> thanks in advance for any answer.
>
> map head . group
>
> Bob



Reply | Threaded
Open this post in threaded view
|

repetition

Luca Ciciriello
In reply to this post by Thomas Davie
My mistake, I haven't specified that the starting list is ordered.

Luca
On Aug 4, 2011, at 11:39 AM, Thomas Davie wrote:

>
> On 4 Aug 2011, at 10:36, Lyndon Maydwell wrote:
>
>> nub
>
> Heh, our differing answers point out an ambiguity in the question.
>
> Luca, given [5,10,10,5] what is this function expected to produce?
>
> if you want [5,10] then nub is correct.
> if you want [5,10,5] then map head . group is correct.
>
> Bob
>



Reply | Threaded
Open this post in threaded view
|

repetition

Henk-Jan van Tuyl
In reply to this post by Luca Ciciriello
On Thu, 04 Aug 2011 11:31:02 +0200, Luca Ciciriello  
<luca_ciciriello at hotmail.com> wrote:

> Hi All.
> Is there any function in Prelude that removes the repeated elements in a  
> list?
>
> In example I've a list like this one: xs =  
> ["3","3","3","3","3","4","4","4","4","4","5","5","5","5","5","6","6","6","6","6","6","6"]
>
> I need a function f such that f xs = ["3","4","5","6"]
>

Not in Prelude, but in Data.List:
   nub

Prelude Data.List> nub  
["3","3","3","3","3","4","4","4","4","4","5","5","5","5","5","6","6","6","6","6","6","6"]
["3","4","5","6"]

Regards,
Henk-Jan van Tuyl


--
http://Van.Tuyl.eu/
http://members.chello.nl/hjgtuyl/tourdemonad.html
--


Reply | Threaded
Open this post in threaded view
|

repetition

Daniel Fischer
In reply to this post by Luca Ciciriello
On Thursday 04 August 2011, 11:44:31, Luca Ciciriello wrote:
> My mistake, I haven't specified that the starting list is ordered.

Then

map head . group

has the lower time complexity and does what you want.
Since nub has the type

nub :: Eq a => [a] -> [a]

its time complexity is O(n*d) where n is the length of the input list and d
the number of distinct elements in the list, so generally it has quadratic
behaviour.
map head . group has linear [O(n)] behaviour, thus scales better. But it
produces different output in general.

If the types you need to handle are instances of Ord, not only of Eq, you
can use that to write functions with a better time complexity.
Two very simple functions that remove duplicates and sort the input list
are

import Data.List

ordNub1 :: Ord a => [a] -> [a]
ordNub1 = map head . group . sort


import qualified Data.Set as S

ordNub2 :: Ord a => [a] -> [a]
ordNub2 = S.toAscList . S.fromList
-- currently at least, S.toList is the same as S.toAscList,
-- but that's not guaranteed, although unlikely to change

Both have O(n*log d) time complexity, but generally ordNub2 is faster.

If you want the order in which the distinct elements appear in the input
list to be preserved, like nub does, you can use

import qualified Data.Set as S

ordNub3 :: Ord a => [a] -> [a]
ordNub3 = go S.empty
  where
    go st (x:xs)
      | x `S.member` st = go st xs
      | otherwise = x : go (S.insert x st) xs
    go _ [] = []

which also has O(n*log d) time complexity.

>
> Luca
>
> On Aug 4, 2011, at 11:39 AM, Thomas Davie wrote:
> > On 4 Aug 2011, at 10:36, Lyndon Maydwell wrote:
> >> nub
> >
> > Heh, our differing answers point out an ambiguity in the question.
> >
> > Luca, given [5,10,10,5] what is this function expected to produce?
> >
> > if you want [5,10] then nub is correct.
> > if you want [5,10,5] then map head . group is correct.
> >
> > Bob



Reply | Threaded
Open this post in threaded view
|

repetition

Luca Ciciriello
Ok, thanks.

Luca.

On Aug 4, 2011, at 12:34 PM, Daniel Fischer wrote:

> On Thursday 04 August 2011, 11:44:31, Luca Ciciriello wrote:
>> My mistake, I haven't specified that the starting list is ordered.
>
> Then
>
> map head . group
>
> has the lower time complexity and does what you want.
> Since nub has the type
>
> nub :: Eq a => [a] -> [a]
>
> its time complexity is O(n*d) where n is the length of the input list and d
> the number of distinct elements in the list, so generally it has quadratic
> behaviour.
> map head . group has linear [O(n)] behaviour, thus scales better. But it
> produces different output in general.
>
> If the types you need to handle are instances of Ord, not only of Eq, you
> can use that to write functions with a better time complexity.
> Two very simple functions that remove duplicates and sort the input list
> are
>
> import Data.List
>
> ordNub1 :: Ord a => [a] -> [a]
> ordNub1 = map head . group . sort
>
>
> import qualified Data.Set as S
>
> ordNub2 :: Ord a => [a] -> [a]
> ordNub2 = S.toAscList . S.fromList
> -- currently at least, S.toList is the same as S.toAscList,
> -- but that's not guaranteed, although unlikely to change
>
> Both have O(n*log d) time complexity, but generally ordNub2 is faster.
>
> If you want the order in which the distinct elements appear in the input
> list to be preserved, like nub does, you can use
>
> import qualified Data.Set as S
>
> ordNub3 :: Ord a => [a] -> [a]
> ordNub3 = go S.empty
>  where
>    go st (x:xs)
>      | x `S.member` st = go st xs
>      | otherwise = x : go (S.insert x st) xs
>    go _ [] = []
>
> which also has O(n*log d) time complexity.
>
>>
>> Luca
>>
>> On Aug 4, 2011, at 11:39 AM, Thomas Davie wrote:
>>> On 4 Aug 2011, at 10:36, Lyndon Maydwell wrote:
>>>> nub
>>>
>>> Heh, our differing answers point out an ambiguity in the question.
>>>
>>> Luca, given [5,10,10,5] what is this function expected to produce?
>>>
>>> if you want [5,10] then nub is correct.
>>> if you want [5,10,5] then map head . group is correct.
>>>
>>> Bob
>
>