list comprehension unique values

Question

I'm wondering how to obtain the unique values from a list by using Haskell list comprehension. So if I were to enter [2,4,5,4,4,6,2] it would return [2,4,5,6].

Initially I started with unique (y:ys) = [x | x <- (y:ys)] and I know I need some other condition on x, but am not sure how to get there.

Don’t do that with a list comprehension, just use [the `nub` function](https://hackage.haskell.org/package/base-4.10.0.0/docs/Data-List.html#v:nub). Or, potentially even better, depending on your use case, use a [`Set`](https://hackage.haskell.org/package/containers-0.5.10.2/docs/Data-Set.html#t:Set) instead of a list. — Alexis King, Jul 24 '17 at 08:41
Yes, but I'm trying to practice and solve it without built in functions — MandyLB, Jul 24 '17 at 08:49
This is not possible using just guard clauses in a list comprehension. These are confined to a "local" perspective, looking at just one element at a time. To exclude elements based on the remainder of the input, you will need some other construct, such as `nub` or a fold. — amalloy, Jul 24 '17 at 09:21
If you want to avoid library functions, you have to reimplement them in some form. Define first a function which given `x` and `ys` removes all the occurrences of `x` in the list `ys`. Then use recursion to scan the list and remove duplicates. This amount to rewriting `nub` on your own. — chi, Jul 24 '17 at 09:30

score 9 · Answer 1 · answered Jul 24 '17 at 09:53

The comment from @amalloy that list comprehensions are confined to a "local" perspective is the key insight here. There is a sensible way to write nub as a list comprehension, but you first need to change your perspective.

An often useful function sadly omitted from the library is the function which decorates each element of a list with its context.

picks :: [x] -> [([x], x, [x])]
picks []       = []
picks (x : xs) = ([], x, xs) : [(x : bs, y, as) | (bs, y, as) <- picks xs]

So

picks [1,2,3] =
[([],1,[2,3]), ([1],2,[3]), ([1,2],3,[])]

Each element of the list is put in the middle of a triple, with the elements 'before' to its left and the elements 'after' to its right.

This answer of mine explains the deep structure which makes picks in some sense a "standard" operation, derivable from the structure of lists. But we don't need that background information to deploy it.

The picks function gives us exactly the contextual information we need to write nub as a list comprehension. All we need to do is pick out the elements which don't occur in their own 'before lists'.

myNub :: Eq x => [x] -> [x]
myNub xs = [x | (bs, x, as) <- picks xs, not (elem x bs)]

I make no promises as to the efficiency of this operation, but I do like the clarity that comes from combining list comprehensions with extra spatial context.

score 0 · Answer 2 · answered Jul 25 '17 at 00:33

You could do it in a (perhaps needlessly clever) way with laziness, by starting with a bit of circular reasoning: each element of the input should appear in the output, only if it hasn’t appeared in the output.

That is, for an input list like [0, 0, 1], the first 0 should be added but the second 0 should not.

Clearly, something like this won’t work:

unique xs = us
  where us = [x | x <- xs, x `notElem` us]

Because it will get stuck in an infinite loop, trying to test elements of the output that haven’t been generated yet. What you can do instead is change the reasoning to this: each element of the input should appear in the output, only if it hasn’t already appeared in the output.

You can implement this directly by considering what “already” means: the current value must not have appeared at an index before the current index.

unique xs = catMaybes us
  where
    us =
      [ if Just x `elem` take i us  -- If the element has appeared before here
        then Nothing                -- then don’t include it again
        else Just x                 -- otherwise do include it.
      | (i, x) <- zip [0..] xs      -- (Zip the elements with their indices.)
      ]

So for the input list xs = [0, 0, 1], this would generate xs' = [Just 0, Nothing, Just 1], which would be flattened by catMaybes into [0, 1]. Testing with QuickCheck confirms this is equivalent to nub, and halts because we only check the first take i elements of us at each step, ensuring that we don’t examine any elements that haven’t been generated yet.

It’s worth noting that, like nub, this is O(n²) in the length of the input.

list comprehension unique values

2 Answers2