[Haskell-cafe] Cartesian product of a Set

[Joachim Breitner]

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