Working with list of lists in Prolog

Question

Please help me to solve this problem: I have a list of lists

[[1,2],[3,4]]

How do I get:

[1,3]

[1,4]

[2,3]

[2,4]

Or if I have a list of lists

[[1,2],[3,4],[6,7]]

How do I get:

[1,3,6]

[1,3,7]

[1,4,6]

[1,4,7]

[2,3,6]

[2,3,7]

[2,4,6]

[2,4,7]

Solution 1

You can do something like this:

lists([], []).
lists([[Head|_]|Lists], [Head|L]):-
  lists(Lists, L).
lists([[_,Head|Tail]|Lists], L):-
  lists([[Head|Tail]|Lists], L).

That is, take the first element of the first list in your input list and continue recursively with the remaining lists. As a second chance, skip that element and redo with the remaining elements.

Solution 2

The predicate for accessing a single list element is the most basic Prolog building block: member/2.

And you want a list of all lists' elements: maplist/3 does such mapping. Thus we can write

combine(Ls, Rs) :-
    maplist(get1, Ls, Rs).
get1(L, E) :-
    member(E, L).

note that get1/2 is only required so that we swap the member/2 arguments. But because in (pure) Prolog we are describing relations between arguments, we can swap arguments' order and simplify it even more:

combine(Ls, Rs) :-
    maplist(member, Rs, Ls).

Test output:

?- combine( [[1,2],[a,b]], Xs).
Xs = [1, a] ;
Xs = [1, b] ;
Xs = [2, a] ;
Xs = [2, b].

%% this is the same as:
       %% maplist( member, Xs, [[1,2],[a,b]]) :-
       %%          member( X1,  [1,2]      ),
       %%          member( X2,        [a,b]),  Xs = [X1,X2].

edit

A joke: really, my first combine/2 should have been written like

combine(Ls, Rs) :-
    maplist(rebmem, Ls, Rs).
rebmem(L, E) :-
    member(E, L).

Comments

[DaveEdelstein]

i believe this is called the cartesian product

[DaveEdelstein]

great use of member & maplist! very impressive!

[rnso]

Why this command: findall(X, maplist(member, [[a,b,c], [1,2,3]], X), L). gives infinite output?

[CapelliC]

@mso: member/2 has a list as second argument. Otherwise it 'builds up' it on backtracking, hence it doesn't terminate when driven by findall

[Will Ness]

a little gem, this thing is. :)