Implementing nub (distinct)

Question

I've implemented the following nub' or "give distinct elements of list" function:

nub' :: (Eq a) => [a] -> [a]
nub' [] = []
nub' xs = nubHelper xs []

nubHelper :: (Eq a) => [a] -> [a] -> [a]
nubHelper []     acc = acc
nubHelper (y:ys) acc = if(contains y acc)  
                         then nubHelper ys acc 
                         else nubHelper ys (acc ++ [y])
                         where contains match acc = 
                            foldl (\as x -> if(y == x) then True else as) False acc

Example:

*Main> nub' [1,2,1,1,1,1,3,4,3,1]
[1,2,3,4]

Surely there must be a cleaner way?

Answer 1

For the "official" answer, you can go straight to the GHC source for nub:

nub                     :: (Eq a) => [a] -> [a]
nub l                   = nub' l []
  where
    nub' [] _           = []
    nub' (x:xs) ls
        | x `elem` ls   = nub' xs ls
        | otherwise     = x : nub' xs (x:ls)

Some of the differences that stand out are:

• Use a where clause to scope your helper function, and name it with a "prime" symbol. In your case, I guess the helper would be nub''. The helper's type can then be automatically inferred.
• Use pattern matching instead of if-then-else.
• Your contains helper is just the elem builtin. They chose to write x `elem` ls instead of elem x ls, probably to read more smoothly.
• It's more natural / efficient to prepend than to append elements to a list. Instead of building acc as the result as a list of wanted elements, they build ls as the list of elements to exclude in future encounters.

Answer 2

3 lines using filter.

nub' :: (Eq a) => [a] -> [a]
nub' [] = []
nub' (x:xs) = x : nub' (filter (/=x) xs)

Explanation

What I'm doing here can be explained in the following:

1. Separate the input as x:xs using pattern matching. So, x is the first lement of the list and xs will be rest of the list.
2. Concat the first element x with a nub of filtered list of xs that do not contain x.

Performance

In terms of performance, I'm not sure if this is the same as the one implemented in the GHC source code.