is it possible to have a set comprehension in haskell?

Question

In Haskell we have list generators, such as:

[x+y | x<-[1,2,3], y<-[1,2,3]]

with which we get

[2,3,4,3,4,5,4,5,6]

Is it possible to have a set generator which doesn't automatically add an element if it is already in the list?

In our example we would obtain:

[2,3,4,5,6]

If so, how? If it is not already implemented, how would you implement it?

Answer 1

Haskell can do this, but not quite out-of-the-box.

The basic underpinning is that a list comprehension can also be written as a monadic binding chain, in the list monad:

Prelude> [x+y | x<-[1,2,3], y<-[1,2,3]]
[2,3,4,3,4,5,4,5,6]
Prelude> [1,2,3] >>= \x -> [1,2,3] >>= \y -> return (x+y)
[2,3,4,3,4,5,4,5,6]

...or, with better readable do-syntax (which is syntactic sugar for monadic binding)

Prelude> do x<-[1,2,3]; y<-[1,2,3]; return (x+y)
[2,3,4,3,4,5,4,5,6]

In fact, there's a language extension that also turns all list comprehensions into syntactic sugar for such a monadic chain. Example in the tuple (aka writer) monad:

Prelude> :set -XMonadComprehensions 
Prelude> [x+y | x <- ("Hello", 4), y <- ("World", 5)] :: (String, Int)
("HelloWorld",9)

So really, all we need is a set monad. This is sensible enough, however Data.Set.Set is not a monad on Hask (the category of all Haskell types) but only only the subcategory that satisfies the Ord constraint (which is needed for lookup / to avoid duplicates). In the case of sets, there is however a hack that allows hiding that constraint from the actual monad instance; it's used in the set-monad package. Et voilà:

Prelude Data.Set.Monad> [x+y | x<-fromList[1,2,3], y<-fromList[1,2,3]]
fromList [2,3,4,5,6]

The hack that's needed for instance Monad Set comes at a price. It works like this:

{-# LANGUAGE GADTs, RankNTypes #-}
import qualified Data.Set as DS

data Set r where
  Prim :: (Ord r => DS.Set r) -> Set r
  Return :: a -> Set a
  Bind   :: Set a -> (a -> Set b) -> Set b
  ...

What this means is: a value of type Data.Set.Monad.Set Int does not really contain a concrete set of integers. Rather, it contains an abstract syntax expression for a computation that yields a set as the result. This isn't great for performance, in particular it means that values won't be shared. So don't use this for big sets.

There's a better option: use it directly as a monad in the proper category (which only contains orderable types to begin with). This unfortunately requires even more language-bending, but it's possible; I've made an example in the constrained-categories library.

Answer 2

If your values can be put in Data.Set.Set (i.e. they are in class Ord) you can just apply Data.Set.toList . Data.Set.fromList to your list:

Prelude> import Data.Set
Prelude Data.Set> Data.Set.toList . Data.Set.fromList $ [x+y | x<-[1,2,3], y<-[1,2,3]]
[2,3,4,5,6]

The complexity of this would be O(n log n).

If the type obeys (Eq a, Hashable a), you can use Data.HashSet in much the same way. The average complexity is O(n).

If all you have is Eq, you have to get by with something like Data.List.nub:

Prelude> import Data.List
Prelude Data.List> nub [x+y | x<-[1,2,3], y<-[1,2,3]]
[2,3,4,5,6]

but the complexity is inherently quadratic.