Scheme - Cartesian product with 'map'?

Question

I am trying to write a function that returns the cartesian product of 2 sets (lists) with the help of the 'map' function and I want each pair of elements in the returned list to be a vector.

(cartesian-product '(1 2 3) '(a b))

'(#(3 a) #(3 b) #(2 a) #(2 b) #(1 a) #(1 b))

My initial idea was to make a separate procedure that makes a vector out element c (constant) in set 2 and element n in set 1 where element n changes for each iteration and then proceed to map this separate function with set 2. So for example, if I use the above lists (in the code sample) I would get 3 different vectors from this separate function:

#'(a 1) #'(a 2) #'(a 3)

And when using map on this I would get the result:

'(#'(a 1) #'(a 2) #'(a 3) #'(b 1) #'(b 2) #'(b 3))

But I realized that I would instead get a result that looks something like this:

'((#'(a 1) #'(a 2) #'(a 3)) (#'(b 1) #'(b 2) #'(b 3)))

because the separate function has to be recursive and it would have to return a list when finished.

Now I am back to square one and I am out of ideas. Help please... Should mention that this is a school assignment and I am not allowed to use any predefined functions except for simple ones like:

cdr,car,cons,map etc

Try to keep it as basic as possible. I have only been using Scheme for like a month so go easy on me :)

Óscar López Óscar López · Accepted Answer · 2016-10-26T19:36:16

We can nest two maps and flatten the result at the end, making sure to create a vector in the right place:

(define (cartesian-product lst1 lst2)
  (apply append
         (map (lambda (x)
                (map (lambda (y)
                       (vector x y))
                     lst2))
              lst1)))

It works as expected:

(cartesian-product '(1 2 3) '(a b))
=> '(#(1 a) #(1 b) #(2 a) #(2 b) #(3 a) #(3 b))

Scheme - Cartesian product with 'map'?

1 Answers