Prolog creating lists

Question

I'm trying to write a program in Prolog that will take in three lists (all of which are the same length) and return a list of lists.

The list of lists that I am returning is a triple that contains elements from the three lists that are being passed in. The first element of the triple is from the first list passed in, the second element of the triple is from the second list, and the third element of the triple is from the third list passed in.

What I want to have happen is the list of triples that the function is returning to return every single possible combination that you could make from the three lists being passed in.

As of now I have some code that takes the first elements of the three lists and makes a triple out of them, then takes the second element of all the lists and makes a triple out of them, and so on. Here it is below.

   listCombos( [], [], [], []).
   listCombos( [A|AREST], [B|BREST], [C|CREST], [[A,B,C]|SOLUTION]) :-
       listCombos( AREST, BREST, CREST, SOLUTION).

My strategy for getting every combo is taking the first element of the first list and the first element in the second list and then going through each elements in the third list. Once I have done that I will move on the the first element in the first list and the second element in the second list and match those up with each element in the third list. Then after I have went through the second list move onto the first list. Let me know if more clarification on this is needed.

I'm new to Prolog so I don't understand how to turn what I'm planning to do into code. I've tried a few things but haven't been successful and have gotten some error codes I don't understand so it's hard to tell if I'm going in the right direction (I can post some of my attempts if needed). If anyone has some idea of what direction I should go in or some explanation on what I need to do that would be appreciated.

Thank you very much.

Answer 1

We first can solve a related problem: given a list of "heads" Hs and a list of "tails" Ts, construct all lists for all heads H in Hs, and all tails T in Ts in a list. We can do this with a predicate:

merge_all([], _, []).
merge_all([H|Hs], Ts, All) :-
    merge_single(Ts, H, All, D),
    merge_all(Hs, Ts, D).

merge_single([], _, D, D).
merge_single([T|Ts], H, [[H|T]|Rest], D) :-
    merge_single(Ts, H, Rest, D).

For example:

?- merge_all([a, b], [[1, 4], [2, 5]], R).
R = [[a, 1, 4], [a, 2, 5], [b, 1, 4], [b, 2, 5]].

Now we can use this for example to make all cross products with Cs and the "empty set", for example if Cs = [a, b, c], then:

?- merge_all([a, b, c], [[]], RC).
RC = [[a], [b], [c]].

Given we have this result, we can make the cross product of Bs with this result. For example if Bs = [1, 4], then we obtain:

?- merge_all([a, b, c], [[]], RC), merge_all([1, 4], RC, RB).
RC = [[a], [b], [c]],
RB = [[1, a], [1, b], [1, c], [4, a], [4, b], [4, c]].

With the above generating the cross product of three sets should be straightforward, I leave this as an exercise.

Answer 2

It's advisable to generalize the construct you're looking for, accepting a list of lists to be combined, following the schema from this answer:

combine(Ls,Rs) :- maplist(member,Rs,Ls).
listCombos(A,B,C, SOLUTION) :- findall(R,combine([A,B,C],R),SOLUTION).

Answer 3

The approach by Daniel Lyons is good in that it allows us to easily control the order of combinations in the cross-product of a list of lists, while keeping the order of elements in the combinations the same, of course:

cross( [], [[]] ).
cross( [XS | T], R ):- 
    cross(   T,                     TC),
    findall( [X | Y], (                      %       or:
                         member( Y, TC),     %  member( X, XS)  
                         member( X, XS)      %  member( Y, TC),
                      ), 
                 R).

It exhibits good modularity and separation of concerns: the order of presentation is independent of the order of generation and the order of selection.

Answer 4

Knowing a little Prolog the most obvious solution is something like this:

listCombos(Xs, Ys, Zs, Result) :-
    findall([X,Y,Z], 
            (member(X, Xs), member(Y, Ys), member(Z, Zs)),
            Result).