[Haskell-cafe] Cartesian product of a Set

[Dan Weston]

Since S.toAscList x is sorted (and yes, as another poster points out, 
you should use toAsciList to get that sorting guarantee), you can prove 
that your cartesian product list is also sorted.

Data.Set will almost certainly always have access to the sorted list, 
but even if not, length x < length (cartesian x) for any nonempty list 
(n vs. n^2), so it's worth forcing it to sort.

The Prelude defines the instance (Ord a, Ord b) => Ord (a, b), with the 
obvious lexicographic ordering that your list comprehension generates 
(fst varying more slowly than snd):

   sorted(xs) ==> sorted [(i,j) | i <- xs, j <- xs]

 >> This is *not* true if the generators are reversed:
 >>  BAD:  sorted(xs) =/=> sorted [(i,j) | j <- xs, i <- xs]

This allows you to safely say:

cartesian x = S.fromDistinctAscList [(i,j) | i <- xs, j <- xs]
    where xs = S.toAscList x
    -- fromDistinctAscList sorted precondition satisfied by construction

with full confidence that (cartesian x) is a well-constructed set. It 
may be worth adding a comment that you have fulfilled your proof 
obligation in calling fromDistinctAscList, so others aren't left wondering.

Dan

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