Functional, tail-recursive way to generate all possible combinations from a dictionary and a dimension

Question

I'd like to find out concise, functional and tail-recursive (if possible) way of implementing the below specified function:

(define (make-domain digits dimension)
    ;; Implementation)
;; Usage
(make-domain '(0 1) 0) => (())
(make-domain '(0 1) 1) => ((0) (1))
(make-domain '(0 1) 2) => ((0 0) (0 1) (1 0) (1 1))
(make-domain '(0 1) 3) => ((0 0 0) (0 0 1) (0 1 0) (0 1 1) (1 0 0) (1 0 1) (1 1 0) (1 1 1))

I'd prefer Scheme implementation with as few helper or library functions as possible, but SML or Haskell will do as well. I'm trying to find a tail-recursive solution possibly using mutual or nested recursion, but with no luck at the moment.

Thank you very much!

Answer 1

Your answer can be made tail-recursive by the usual trick of using an accumulator. The following is Racket not Scheme, but perhaps only because it uses append* which can be defined, I think, as

(define (append* . args)
  (apply append args))

Here is a tail-recursive version, therefore:

(define (make-domain digits dimension)
  (let mdl ([d dimension] [r '(())])
    (if (zero? d)
        r
        (mdl (- d 1)
             (append* (map (λ (d)
                             (map (λ (sd)
                                    (cons d sd))
                                  r))
                           digits))))))