# [Haskell-cafe] Cartesian product of a Set

ok ok at cs.otago.ac.nz
Thu Aug 2 00:15:35 EDT 2007

```On 2 Aug 2007, at 2:28 am, Andy Gimblett wrote:
> Is this a reasonable way to compute the cartesian product of a Set?
>
>> cartesian :: Ord a => S.Set a -> S.Set (a,a)
>> cartesian x = S.fromList [(i,j) | i <- xs, j <- xs]
>>     where xs = S.toList x

imagine presenting it this way:

cartesian s = S.fromList \$ liftM2 (,) s' s' where s' = S.toList s

There are times to use monads and times not to.  (One wonders whether
S.Set is an instance of Monad, and if not, why not.)

>
> It's a fairly "obvious" way to do it, but I wondered if there were any
> hidden gotchas.  I'm particularly concerned by toList (O(n)) fromList
> (O(n log n)) - but for other reasons I'd really like to be using Set
> rather than List for this (I think).

In fact it's worse than that.  Given a set with n elements, the
Cartesian
product of that set with itself  has n**2 elements, so S.fromList
must take
O(n**2.log(n**2)) = O(n**2.log n) time.

If sets are represented as ordered lists, then the list comprehension
above generates a suitably ordered result.

On the other hand, I've usually found that it pays to avoid explicitly
constructing things like Cartesian products.  Could that be the case
here?

```