Working with list of lists in Prolog – List

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

The Problem:

You have a list of lists of numbers. You want to write a program in Prolog that takes a list of lists as input and returns a list of all the possible pairs of numbers from the list of lists.

For example, if the input is [[1, 2, 3, 4]], the output should be:

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

If the input is [[1, 2, 3, 4, 6, 7]], the output should be:

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

The Solutions:

Solution 1: Using a Recursive Approach

The provided solution leverages a recursive approach to find all possible combinations of elements from a list of lists. The idea is to iteratively traverse the lists, considering each element as a potential starting point for a combination.

The Prolog code for this solution is as follows:

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

Explanation:

1. The first rule defines the base case: if the input list is empty, the output list should also be empty.
2. The second rule handles the case where the first list in the input contains an element. It adds this element to the output list and continues recursively with the remaining lists.
3. The third rule handles the case where the first list in the input does not contain an element. It skips the first element and continues with the remaining elements.

By iteratively applying these rules, the solution effectively explores all possible combinations of elements from the input list of lists.

Solution 2: Using member/2 predicate

Prolog provides a built-in predicate called `member/2` that efficiently checks if an element belongs to a list. To access the elements of individual lists in a list of lists, we can use the `maplist/3` predicate. Combining these two techniques, we can define a predicate `combine/2` as follows:
“`
combine(Ls, Rs) :-
maplist(get1, Ls, Rs).
get1(L, E) :-
member(E, L).
“`
This predicate takes two arguments: `Ls`, a list of lists, and `Rs`, the resulting list of elements. The `maplist/3` predicate iterates through the elements of `Ls`, applying the `get1/2` predicate to each list. The `get1/2` predicate simply checks if an element belongs to the current list using `member/2`.

To simplify the code further, we can swap the arguments of `member/2` and use the following predicate:
“`
combine(Ls, Rs) :-
maplist(member, Rs, Ls).
“`

This version of `combine/2` is more efficient because it avoids the need for an extra predicate like `get1/2`.