ERROR: "Out of global stack" when processing Prolog list of pairs

Question

In SWI-Prolog, I have a list whose elements are pairs of the form Key-ValuesList. For instance, one such list may look like:

[1-[a,b],2-[],3-[c]]

I would like to transform this list into a nested list of pairs of the form Key-[Value], where Value is an element in ValuesList. The above example would be transformed into:

[[1-[a],2-[],3-[c]], [1-[b],2-[],3-[c]]]

My current solution is the following:

% all_pairs_lists(+InputList, -OutputLists).
all_pairs_lists([], [[]]).
all_pairs_lists([Key-[]|Values], CP) :-
  !,
  findall([Key-[]|R], (all_pairs_lists(Values,RCP), member(R,RCP)), CP).
all_pairs_lists([Key-Value|Values], CP) :-
  findall([Key-[V]|R], (all_pairs_lists(Values,RCP), member(V,Value), member(R,RCP)), CP).

Using this predicate, a call of the form

all_pairs_lists([1-[a,b],2-[],3-[c]],OutputLists).

Binds the variable OutputLists to the desired result mentioned above. While it appears correct, this implementation causes an "Out of global stack" error when InputList has very long lists as values.

Is there a less stack consuming approach to doing this? It would seem like quite a common operation for this type of data structure.

m09 m09 · Accepted Answer · 2012-08-07T10:38:54

Well, to sum it up, you're doing it wrong.

In Prolog, when we want to express a relation instead of a function (several results possible instead of one), we don't use findall/3 and member/2 directly. We rather state what the relation is and then maybe once it's done if we need a list of results we use findall/3.

Here what it means is that we want to express the following relation:

Take a list of Key-Values and return a list of Key-[Value] where Value is a member of the Values list.

We could do so as follows:

% The base case: handle the empty list
a_pair_list([], []).

% The case where the Values list is empty, then the resulting [Value] is []
a_pair_list([Key-[]|List], [Key-[]|Result]) :-
    a_pair_list(List, Result).
% The case where the Values list is not empty, then Value is a member of Values.
a_pair_list([Key-[Not|Empty]|List], [Key-[Value]|Result]) :-
    member(Value, [Not|Empty]),
    a_pair_list(List, Result).

Once this relation is expressed, we can already obtain all the info we wish:

?- a_pair_list([1-[a, b], 2-[], 3-[c]], Result).
Result = [1-[a], 2-[], 3-[c]] ;
Result = [1-[b], 2-[], 3-[c]] ;
false.

The desired list is now just a fairly straight-forward findall/3 call away:

all_pairs_lists(Input, Output) :-
    findall(Result, a_pair_list(Input, Result), Output).

The important thing to remember is that it's way better to stay away from extra logical stuff: !/0, findall/3, etc... because it's often leading to less general programs and/or less correct ones. Here since we can express the relation stated above in a pure and clean way, we should. This way we can limit the annoying use of findall/3 at the strict minimum.

ERROR: "Out of global stack" when processing Prolog list of pairs

2 Answers