Removing duplicates from a list in Haskell without elem

by

Both your code and nub have O(N^2) complexity.

You can improve the complexity to O(N log N) and avoid using elem by sorting, grouping, and taking only the first element of each group.

Conceptually,

rmdups :: (Ord a) => [a] -> [a]
rmdups = map head . group . sort

Suppose you start with the list [1, 2, 1, 3, 2, 4]. By sorting it, you get, [1, 1, 2, 2, 3, 4]; by grouping that, you get, [[1, 1], [2, 2], [3], [4]]; finally, by taking the head of each list, you get [1, 2, 3, 4].

The full implementation of the above just involves expanding each function.

Note that this requires the stronger Ord constraint on the elements of the list, and also changes their order in the returned list.

More Related Contents:

  1. Using Haskell’s map function to calculate the sum of a list
  2. Haskell finding mean of cubes of odd members Any ideas? [closed]
  3. Histogram in Haskell [closed]
  4. What is Haskell’s Stream Fusion
  5. Using return vs. not using return in the list monad
  6. Cartesian product of infinite lists in Haskell
  7. Decrementing ranges in Haskell
  8. Zip with default value instead of dropping values?
  9. Replace individual list elements in Haskell?
  10. How to recursively reverse a list using only basic operations?
  11. Need to partition a list into lists based on breaks in ascending order of elements (Haskell)
  12. Merging two lists in Haskell
  13. Haskell Monad – How does Monad on list work?
  14. Is there a function to flatten a nested list of elements?
  15. Understanding a recursively defined list (fibs in terms of zipWith)
  16. Removing syntactic sugar: List comprehension in Haskell
  17. Counting unique elements in a list
  18. Unsequence Monad function within Haskell
  19. Grouping a list into lists of n elements in Haskell
  20. Why are difference lists more efficient than regular concatenation in Haskell?
  21. Prolog: Filtering a list?
  22. How to generate all the permutations of elements in a list one at a time in Lisp?
  23. Scala list concatenation, ::: vs ++
  24. Segregating Lists in Prolog
  25. How to obtain a nested HTML list from object’s array recordset?
  26. Implications of foldr vs. foldl (or foldl’)
  27. How to flatten all items from a nested Java Collection into a single List?
  28. Python: find a list within members of another list(in order)
  29. How to convert a java.util.List to a Scala list
  30. How to count items’ occurence in a List

Leave a Comment