Improving my inelegant Haskell deduplication function

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, 2018 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. Jul 15, 2018 at 20:48
• might be worth discussing the complexity? in particular why laziness helps here
– jk.
Jul 16, 2018 at 11:13