[Haskell-beginners] repetition

[Daniel Fischer]

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