[Haskell-cafe] Cartesian product of a Set

[Andy Gimblett]

On Thu, Aug 02, 2007 at 04:15:35PM +1200, ok wrote:
> 
> On the other hand, I've usually found that it pays to avoid
> explicitly constructing things like Cartesian products.  Could that
> be the case here?

Quite possibly, though for my purposes I don't _think_ it's worth
routing around it.

I'm using it in a naive (and intentionally so) algorithm to search for
"local top elements" in a partial order.  That is, we require that the
PO satisfies the property:

    for all a,b,c in PO . a <= b and a <= c
                    =>
         exists d in PO . b <= d and c <= d

where a is a "local bottom element" for b and c, and d is the
corresponding "local top element".  Given a PO, for every such a, I
want the set of corresponding d's.  If any such set is empty, a big
red "NO" lights up elsewhere in the program.

My algorithm is the simplest thing I could think of that works:
represent the PO as a Set of (a,a), then simply search its cartesian
product, a Set of ((a,a),(a,a)), for elements of the right shape.  It
works, in only a few lines of code, and really looks a lot like the
definition given above.

It also seems to be fast enough for reasonably sized examples - for a
PO with ~40 elements it's instantaneous.  That's at the bottom end of
"realistic" for my application, and I need to check it for ~100
elements (which is more like my reality), but I think it ought to be
fine/usable.

If, with real data, it turns out to be too slow then yes, I'll ditch
this naive method and look at graph algorithms, which is of course the
Smart thing to do.  However, it's beautiful (to me) code right now,
which strongly reflects the definition of the problem, so I'd be happy
not to.  :-)

Cheers,

-Andy

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