Nice X-Files reference (I think). Here is one approach:

Suppose you want the Cartesian product S0 × S1 ×... × Sn and have already computed (S1 ×... × Sn) as a list L of tuples, each tuple being a list of n elements. You can augment L to become a valid product S0 × (S1 ×... × Sn) by appending together one copy of L, for each x in S0, where x is prepended to each tuple already in L. In other words, add a new leftmost column to the tuples. Scheme code:

(define (cartesian . sets)
  (fold-right (lambda (set tuples)
        (append-map! (lambda (element)
                   (map (cute cons element <>) tuples))
                 set))
          '(())
          sets))

To work on set objects directly you'd need to change "set))" to "(set->list set)))".

Best regards,
Kevin Wortman