current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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