Using a goal on the combinations of items in a list

Nice to know
1

When working with a list sometimes there is a need to check that each item in a list is unique. This requires checking each pair of items. After a while the need to change the goal (unique) to another goal is desired.

Here is some simple code that fills that need.

goal_list_combination(_,[]) :- !.
goal_list_combination(_,[_]) :- !.
goal_list_combination(Goal,[H0,H|T]) :-
    goal_list_combination(Goal,H0,[H|T]),
    goal_list_combination(Goal,[H|T]).

goal_list_combination(_,_,[]) :- !.
goal_list_combination(Goal,H0,[H|T]) :-
    call(Goal,H0,H),
    goal_list_combination(Goal,H0,T).

Here is the goal for unique.

unique(A,B) :-
    A \= B.

While an example run using the goal unique is useful, it does not really demonstrate what is happening.

?- goal_list_combination(unique,[1,2,3,4]).
true.

?- goal_list_combination(unique,[1,2,2,4]).
false.

Using a less practical goal (write_values) to write out the pairs gives some insight into what is happening.

Goal: write_values

write_values(A,B) :-
    format('~w,~w~n',[A,B]).

Example run using the goal write_values.

?- goal_list_combination(write_values,[1,2,3,4]).
1,2
1,3
1,4
2,3
2,4
3,4
true.

When looked at as part of a square matrix, it reveals that this is similar to an upper triangular matrix without the 0s and the diagonal.

  1    2    3    4
1    1,2  1,3  1,4
2         2,3  2,4
3              3,4
4

The predicate was only created for mode goal_list_combination(+,+).

2

I am not sure but I think that this is the same as:

list_pairs(List, X, Y) :-
    append(_, [X|Rest], List),
    select(Y, Rest, _).

You could use select/3 one more time, instead of append/3, if (x_a, x_b) \neq (x_b, x_a).

You can use the usual predicates to go over all pairs, for example:

?- forall(list_pairs([1,2,3,4], X, Y), dif(X, Y)).
true.

?- forall(list_pairs([1,2,2,4], X, Y), dif(X, Y)).
false.

?- forall(list_pairs([1,2,3,4], X, Y), format("~w,~w~n", [X, Y])).
1,2
1,3
1,4
2,3
2,4
3,4
true.

In some cases you might need foreach/2 instead of forall/2 I guess?

3

Thanks. :slightly_smiling_face:

Nice to see different ways to do this.

While I like your variation, how would you get it to work while passing in a goal?

4

Like this (I fixed select/3 to member/2):

foreach_pair(Pred, List) :-
    forall(
        (   append(_, [X|Rest], List),
            member(Y, Rest)
        ),
        call(Pred, X, Y)).

But I really don’t see why you would want to pass the goal to the traversal predicate. Because Prolog has the “lazy evaluation” with backtracking, there is no difference whether you pass the goal or evaluate it outside of the loop.

5

I suppose I could do it that way but this was the first variation I came up with that worked.