Sign up ×

What is an example of a recursive function to compute all possible combinations of lists? For example, (combine (list 1 2 3) (list 1 2)) should return '((1 1) (1 2) (2 1) (2 2) (3 1) (3 2)).

share|improve this question
possible duplicate of Cartesian product in Scheme – Chris Jester-Young Apr 5 '11 at 3:10
BTW, the inner lists aren't quoted. You should expect to get '((1 1) (1 2) (2 1) (2 2) (3 1) (3 2)). – Chris Jester-Young Apr 5 '11 at 3:12
My solution for 2 lists in 3 lines:… – knivil Apr 5 '11 at 10:40

2 Answers 2

up vote 2 down vote accepted

Here's my solution. Requires SRFIs 1 and 26 to be available.

(define (cartesian-product first . rest)
  (define (iter l result)
    (define (prepend-all x)
      (map (cut cons <> x) l))
    (concatenate (map prepend-all result)))
  (map reverse (fold iter (map list first) rest)))
share|improve this answer

Here's my take; I first define a helper concat/map, which takes a list and a function. Like regular map, it applies that function to each element in the list. Unlike map, though, it uses append to combine the results rather than cons. This is useful because we want to get back a single level of lists as an answer:

(define concat/map
  (lambda (ls f)
      [(null? ls) '()]
      [else (append (f (car ls)) (concat/map (cdr ls) f))])))

Then, writing combine for two lists is straightforward. You take each element of the first list, then make every list combining it and an element x from the second list. Since this gives back a list of answers for each element in the first list, use concat/map to put it together as we want:

(define combine
  (lambda (xs ys)
    (concat/map xs (lambda (x)
                     (map (lambda (y) (list x y)) ys)))))

The version of combine that operates on one or more lists, let's call it combine*, is a bit trickier. Instead of making all the lists combining x with the elements from the second list, we just recursively ask for the product of all the remaining ys, and then cons x onto each of those results. The recursion stops when there's only two lists to combine, and uses the original combine in that case.

(define combine*
  (lambda (xs . ys*)
      [(null? ys*) (map list xs)]
      [(null? (cdr ys*)) (combine xs (car ys*))]
      [else (concat/map xs (lambda (x)
                             (map (lambda (y) (cons x y))
                                  (apply combine* ys*))))])))

As a bonus, this pattern of using concat/map to do some work and combine the resulting answers is actually the list monad. It's simplified here, but the structure is in place.

share|improve this answer
(a) In scheme "concat" is rarely used, "append" is much preferred; (b) your concat/map is also weird in that it gets the list before the function, whereas the order is almost always the other way (to accommodate more list arguments that are used for a function of more thn one input); (c) there's a subtle bug in your combine* -- it'll accept one argument but will break when given one; (d) finally, it would be much easier to write it using case-lambda. – Eli Barzilay Apr 8 '11 at 10:05
@Eli Barzilay my intent with concat/map was to sneak the definition of the list monad's bind into the solution. Good catch on the single list bug. – acfoltzer Apr 8 '11 at 13:04
This is another reason why Scheme et al. is a no go for me: one has to re-invent trivial stuff like list comprehension, which is available in languges that utilize more than round parentheses: [ (a,b) | a <- as, b <- bs ] – Ingo Apr 8 '11 at 13:16
Ingo: That's true for "Scheme", but false for most actual implementations. (That's re the re-inventing point, the parens comment is irrelevant flamebait.) – Eli Barzilay Apr 8 '11 at 18:41
Adam: You could do just the same with append in the name... – Eli Barzilay Apr 8 '11 at 18:41

Your Answer


