[Haskell-cafe] Cartesian product of a Set

[Rodrigo Queiro]

toList generates a sorted list since it is implemented as toList =
toAscList, but it's probably bad form to rely on that.

On 01/08/07, Andy Gimblett <A.M.Gimblett at swansea.ac.uk> wrote:
> 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.  :-)
>
> Thanks!
>
> -Andy
>
> --
> Andy Gimblett
> Computer Science Department
> University of Wales Swansea
> http://www.cs.swan.ac.uk/~csandy/
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>