[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
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?
More information about the Haskell-Cafe
mailing list