Removing duplicates from a list in Haskell without elem
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.
Even easier.
import Data.Set
mkUniq :: Ord a => [a] -> [a]
mkUniq = toList . fromList
Convert the set to a list of elements in O(n) time:
toList :: Set a -> [a]
Create a set from a list of elements in O(n log n) time:
fromList :: Ord a => [a] -> Set a
In python it would be no different.
def mkUniq(x):
return list(set(x)))