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.

• Kevin Meredith: Thanks for this answer, @200_success. Could you please say more to It's more natural / efficient to prepend than to append elements to a list?
• 200_success: Think of them as singly linked lists: manipulating the head is guaranteed to be trivial; operations on the tail might not be. (We don't know exactly how the lists are implemented. There might be optimizations that make operations on the tail efficient, but you shouldn't rely on the existence of such optimizations.) With that in mind, see How to work on lists. Prepend (:) is guaranteed to be a fast operation, but Concatenate (++) isn't.
• Kevin Meredith: thanks. From a style point of view, is the padding, required for each = to align, considered best practice?
• 200_success: I can't really say. The Haskell style guide stays silent on the issue.

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.

• Dan Oberlam: Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process.