Cartesian product.

8 2019-01-11 23:51

The following is a reasonably performant implementation, but it still makes many repeat calls to the same function with the same values meaning that it would benefit massively from memoization. I have to make a sufficiently general version of memoize for this but I'll consider posting it when complete. I'm using the curried function here to avoid any sort of reverse or append of the lists.

(define (cartesian-product . An)
  (let cartesian-product-iter
    ((values (lambda (x) x)) (An An))
    (if (null? An)
      (values '())
        (lambda (x)
            (lambda (y) (values (cons x y)))
            (cdr An)))
        (car An)))))


do not edit these