Removing repeated elements from a list in Haskell

Question

I am a beginner to Haskell. I just wonder how to implement a function to remove the repeat element from an array. for example, [1,1,1,3,4,2,2,3], the result should be [1,3,4,2]. I don't want to use some exist functions like element and implement this by using recursion. My idea is to compare x:xs, if x is a repeat element then do the recursion, else rerun the function. Is that correct and how to implement this by code?

Answer 1

If you cannot assume any ordering between the elements (i.e. you don't know if it's an instance of Ord), then you must use nub like one poster has already mentioned. Unfortunately this is O(n^2).

If your elements implement Ord, then you can sort the list in O(nlog(n)) and then remove adjacent elements recursively (which adds just O(n) to the overall runtime). Something like this:

remove_dups :: (Ord a, Eq a) => [a] -> [a]
remove_dups xs = remove $ sort xs
  where
    remove []  = []
    remove [x] = [x]
    remove (x1:x2:xs)
      | x1 == x2  = remove (x1:xs)
      | otherwise = x1 : remove (x2:xs)

Pretty interesting problem. We often need to do this sort of thing. =)

Edit

I didn't notice the result you gave is not in non-decreasing order. The above code will produce [1,2,3,4] instead, which may not be what you want.

Answer 2

You could take a look at the nub function provided by Haskell.

http://www.haskell.org/onlinereport/list.html

Which is this code:

nub                     :: (Eq a) => [a] -> [a]
nub                      = nubBy (==)

nubBy                   :: (a -> a -> Bool) -> [a] -> [a]
nubBy eq []              = []
nubBy eq (x:xs)          = x : nubBy eq (filter (y -> not (eq x y)) xs)

actually, I found a webpage which shows you a more efficient implementation than the one provided by Haskell: http://buffered.io/posts/a-better-nub/