[Haskell-cafe] Cartesian product of a Set

Joachim Breitner mail at joachim-breitner.de
Wed Aug 1 11:52:10 EDT 2007


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


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