nub

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

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

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

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