7
\$\begingroup\$

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?

\$\endgroup\$
10
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Kevin Meredith Apr 25 '14 at 18:33
  • \$\begingroup\$ 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. \$\endgroup\$ – 200_success Apr 25 '14 at 18:42
  • \$\begingroup\$ thanks. From a style point of view, is the padding, required for each = to align, considered best practice? \$\endgroup\$ – Kevin Meredith Apr 26 '14 at 3:00
  • \$\begingroup\$ I can't really say. The Haskell style guide stays silent on the issue. \$\endgroup\$ – 200_success Apr 26 '14 at 6:49
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Dannnno Apr 20 '18 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.