[Haskell-cafe] Cartesian product of a Set

[ok]

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  
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?