Prolog - Cartesian product calculator

Question

I need to create a Cartesian product calculator for Prolog. It should work like this:

Input: product([1,2,3], [a,b], X).

Output: X = [[1,a],[2,a],[3,a],[1,b],[2,b],[3,b]].

I know there are examples on the Internet, but I wanted to write something myself.

This is my code and I think it's pretty close, but for some reason it doesn't exactly work. Any ideas, guys?

% call new with 4 parameters (so we can keep List1 in memory)
product(L1,L2,L3):- product(L1,L2,L3,L1).

% stop when both List1 and List2 are empty
product([], [], [], []).

% first list is empty, recreate it and work it again with the next element of second list (and shorten memory)
product([], [_|T2], List3, [H4|T4]):-
    product([H4|T4], T2, List3, T4).

%go through first list and always first element of second list to our answer
product([H1|T1], [H2|T2], [[H1,H2]|T3], List4):-
    product(T1, [H2|T2], T3, List4).

Answer 1

As said by Coder (+1), you should change the terminal clause from

product([], [], [], []).

to

product(_, [], [], _).

But ins't enough.

You shuold change che third clause from

product([], [_|T2], List3, [H4|T4]):-
    product([H4|T4], T2, List3, T4).

to

product([], [_|T2], List3, L4):-
    product(L4, T2, List3, L4).

I mean: is an error to consume the saved list 1.

With your version, from

product([1,2,3,4,5], [a,b,c,d], X),

you get only

[[1,a],[2,a],[3,a],[4,a],[5,a],[1,b],[2,b],[3,b],[4,b],[5,b],[2,c],[3,c],[4,c],[5,c],[3,d],[4,d],[5,d]]

That is: you loose [1,c], [1,d] and [2,d].

Answer 2

In SWI-Prolog, it is also possible to generate the Cartesian product using the findall/3 and member/2 predicates:

:- initialization(main).
:- use_module(library(chr)).

main :-
    product([1,2,3], [a,b], X),
    writeln(X).

product(A,B,C) :-
    findall([X,Y],(member(X,A),member(Y,B)),C).

This program prints [[1,a],[1,b],[2,a],[2,b],[3,a],[3,b]].

Answer 3

You should change the clause:

product([], [], [], []).

to:

product(_, [], [], _).

That's because when L2 gets empty it calls product(L1,[],L3,L4) where L1 and L4 are not empty. Your base case must be when L2 gets empty (then L3 gets empty as output list) and other lists may have elements:

?- product([1,2,3], [a,b], X).
X = [[1, a], [2, a], [3, a], [1, b], [2, b], [3, b]] ;
false.