Hi, Am Mittwoch, den 01.08.2007, 15:28 +0100 schrieb Andy Gimblett:
Hi all,
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
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).
Using only functions from the Set module, you could write:
catesian s = fold (\v prod -> prod `union` map ((,)v) s ) empty s
But this won’t be faster, I guess, as map is O(n·log n) and fold is O(n) OTOH, ((,)v) should be monotonic, so it might be faster (and hopefully still correct) to write:
catesian s = fold (\v prod -> prod `union` mapMonotonic ((,)v) s ) empty s
Greetings, Joachim -- Joachim Breitner e-Mail: mail@joachim-breitner.de Homepage: http://www.joachim-breitner.de ICQ#: 74513189