Making tuples out of two lists

Question

I'm a beginner in Prolog and I have two make tuples out of two lists using recursion. For example, func ([1, 2, 3], [4, 5, 6]) should output [(1, 4), (1,5), (1,6), (2, 4), (2, 5), (2, 6), (3, 4), (3 ,5), (3, 6)]. I have the following code:

func([],_,[]).
func([X|T1],Y,[Z|W]):-
    match(X,Y,Z),
    func(T1,Y,W).

match(X,[Y],[(X,Y)]).
match(X,[Y|T],[(X,Y)|Z]) :-
    match(X,T,Z).

But my output for func([1,2,3],[4,5,6],X) is X = [[(1, 4), (1, 5), (1, 6)], [(2, 4), (2, 5), (2, 6)], [(3, 4), (3, 5), (3, 6)]].

How can I get rid of the extra square brackets in the middle of my output? I've tried playing with the parenthesis and brackets in both of my functions, but I can't figure it out.

Answer 1

Using the findall/3 standard predicate and the member/2 de facto standard predicate:

| ?- findall(X-Y, (member(X,[1,2,3]), member(Y,[4,5,6])), Pairs).

Pairs = [1-4,1-5,1-6,2-4,2-5,2-6,3-4,3-5,3-6]
yes

To understand this solution, observe that, for each value of X, we enumerate by backtracking all values of Y. I.e. when backtracking (as implicitly performed by the findall/3 predicate to construct a list of all solutions of its second argument), we exhaust all solutions for the last choice-point (the member(Y,[4,5,6]) goal) before backtracking to a previous choice-point (the member(X,[1,2,3]) goal). This is know as chronological backtracking and is one of the defining characteristics of Prolog.

Note that I used X-Y, the usual Prolog representation for a pair, instead of (X,Y), which is not a recommended solution for constructing n-tuples as it only works nicely for pairs of elements.