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: [EMAIL PROTECTED] Homepage: http://www.joachim-breitner.de ICQ#: 74513189 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
