[Haskell-cafe] Cartesian product of a Set
Joachim Breitner
mail at joachim-breitner.de
Wed Aug 1 11:52:10 EDT 2007
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 at joachim-breitner.de
Homepage: http://www.joachim-breitner.de
ICQ#: 74513189
More information about the Haskell-Cafe
mailing list