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?