# [plt-scheme] re: the fastest way to calc a cartesian product

Good idea to "remind" people of functional representations of things.
Now do that in Java without getting carpal tunnel :-)
How's Radford? -- Matthias
On Sep 19, 2006, at 1:02 PM, Barland, Ian wrote:
>* This is NOT the answer you were looking for...
*>*
*>* But if you want to allow *infinite* sets, and take "element-of" as
*>* your only
*>* primitive (and forgo being able to iterate over elements of the set),
*>* you can represent sets as their element-of (indicator) function.
*>* Then Cartesian-product (and union and intersection) are O(1) :-)
*>*
*>* An uncommented example:
*>* ===========
*>* (define cars (lambda (elt) (memq elt '(vw saab bmw audi))))
*>* (define evens (lambda (elt) (and (number? elt) (even? elt))))
*>*
*>* (define (element-of? elt set) (set elt))
*>*
*>* (define (cartesian-product A B)
*>* (lambda (elt)
*>* (and (length=2? elt)
*>* (element-of? (first elt) A)
*>* (element-of? (first elt) B))))
*>*
*>*
*>* (define (length=2? any)
*>* (and (cons? any)
*>* (cons? (rest any))
*>* (empty? (rest (rest any)))))
*>*
*>* (define evenEuroCars (cartesian-product evens cars))
*>* (element-of? '(4 bmw) evenEuroCars) ; = #t
*>* (element-of? '(bmw 4) evenEuroCars) ; = #f
*>* ==============
*>*
*>* I actually use this in discrete math when introducing sets,
*>* as a tangential way to reinforce data abstraction:
*>* I give them a data definition which allows both lists and functions
*>* as ways to represent Sets.
*>* If they follow the book's math-definition of cartesian-product
*>* word-for-word, they are naturally led to the above code.
*>* If they are focused on the implementation of their inputs, they
*>* instead
*>* gravitate into thinking their inputs are lists, and that therefore
*>* their
*>* output also needs to be a list, and are then stuck with the problem
*>* you are
*>* asking about.
*>*
*>* _________________________________________________
*>* For list-related administrative tasks:
*>* http://list.cs.brown.edu/mailman/listinfo/plt-scheme
*