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?
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
