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

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.