[Haskell-cafe] Cartesian product of a Set

Andy Gimblett A.M.Gimblett at swansea.ac.uk
Wed Aug 1 17:22:38 EDT 2007

On Wed, Aug 01, 2007 at 01:42:52PM -0700, Dan Weston wrote:

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

That'll do it: with that change, my program runs eight times faster;
according to the profiler, it's gone from spending ~85% of its time in
cartesian to ~0%.  :-)

I don't see why my list comprehension always generates a sorted list,
however: toList generates a sorted list?  It doesn't claim to in the
docs.  Do I perhaps need to use toAscList instead?

I happen to have put my data into the Set in order in this example, so
maybe I just lucked out?  Or am I missing something?

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

Lucky me.  :-)



Andy Gimblett
Computer Science Department
University of Wales Swansea

More information about the Haskell-Cafe mailing list