I'm trying to select unique elements from a list like this:
x = [1,1,2,3,4]
s = [e | e <- x, not (e `elem` s)]
It doesn't produce errors, but when I try to read from s it seems like the program hangs. Why?
Plus, what's the right way to do this?
I'm not much of a Haskell-er, but this seems like you've just coded up something sort of like1 Russell's paradox. Aren't you asking for a list s whose elements are those that are in x, but not in s?
s = [e | e <- [1,1,2,3,4], not (e `elem` s)]
So, consider what happens when you try to ask for the first element of s. Well, the first element from e is 1, so 1 will be the first element of s if not (1 `elem` s). Well, is (1 `elem` s)? We can check by iterating over the elements of s and seeing if 1 appeared. Well, let's start with the first element of s…
In general suppose that some n is an element of s. Then what must be true? n must be an element of x (easy to check), and also not an element of s. But we supposed that it was an element of s. This is a contradiction. Therefore, no n can be an element of s, so s must be the empty list. Unfortunately, the Haskell compiler isn't doing the proof that we just did, it's trying to programmatically compute the elements of s.
To remove duplicate items from a list, you want the function that Neil Brown recommended in a comment, nub from Data.List:
O(n^2). The nub function removes duplicate elements from a list. In particular, it keeps only the first occurrence of each element. (The name nub means ‘essence’.) It is a special case of nubBy, which allows the programmer to supply their own equality test.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments