[Haskell-cafe] Cartesian product of a Set

Dan Weston westondan at imageworks.com
Wed Aug 1 16:42:52 EDT 2007

Andy Gimblett wrote:
> 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

Your list comprehension always generates a sorted list, so changing 
S.fromList to its "unsafe" version (but guarateed by you) 
S.fromDistinctAscList should get you back to O(n).

Of course the order of the generators was key (i before j).


More information about the Haskell-Cafe mailing list