I'm working on learning Haskell, and one of the simple exercises I put myself through to this end is writing a function that deduplicates a list, removing all of the duplicate elements of a list such that every element in the output list is both unique and present in the original list.

My inelegant code for doing this is as follows:

dedup [] = []
dedup (n:ns) = theDedup n ns ns
    where theDedup n ns remains
            | ns == [] = n : []
            | remains == [] = n : theDedup (head ns) (tail ns) (tail ns)
            | n == head remains = theDedup (head ns) (tail ns) (tail ns)
            | otherwise = theDedup n ns $ tail remains

For every element of the original list n:ns, theDedup takes that element and recursively compares it to every other (remains), while keeping a copy of the items left to deduplicate as ns. When remains has run out, the current n has been compared to every other value and so must be unique, and when ns has run out, the entire list has been deduplicated, so n must be unique.

This is a rather confusing way of expressing a rather simple algorithm. How can it be done better?


Given the first element of the list, we want to put it into the result, remove it from the rest of the list, and then continue deduplication of the rest. This gives us the following short code:

dedup :: [a] -> [a]
dedup [] = []
dedup (x:xs) = x : dedup (filter (/= x) xs)
  • This site is about conceptual questions and answers are expected to explain things. Throwing code dumps instead of explanation is like copying code from IDE to whiteboard: it may look familiar and even sometimes be understandable, but it feels weird... just weird. Whiteboard doesn't have compiler
    – gnat
    Jul 15 '18 at 20:15
  • The question was: "How can it be done better?" That I answered. But I have now added a bit of explanation of how I came up with my code. I hope that makes my answer better.
    – md2perpe
    Jul 15 '18 at 20:48
  • 1
    might be worth discussing the complexity? in particular why laziness helps here
    – jk.
    Jul 16 '18 at 11:13

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.