[Haskell-cafe] Cartesian product of a Set

Andy Gimblett A.M.Gimblett at swansea.ac.uk
Wed Aug 1 10:28:01 EDT 2007

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).

Many thanks for any thoughts,


Andy Gimblett
Computer Science Department
University of Wales Swansea

More information about the Haskell-Cafe mailing list