[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

Following up on my recent message about (ab)use of monadic operations,
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  
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  

More information about the Haskell-Cafe mailing list