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 |
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 |
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> |
In reply to this post by Thomas Davie
nub
> _______________________________________________ > Beginners mailing list > Beginners at haskell.org > http://www.haskell.org/mailman/listinfo/beginners > |
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 >> > |
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 |
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 |
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 > |
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 -- |
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 |
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 > > |
Free forum by Nabble | Edit this page |