[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

-- 
Andy Gimblett
Computer Science Department
University of Wales Swansea
http://www.cs.swan.ac.uk/~csandy/


More information about the Haskell-Cafe mailing list