Prolog - how to check if a list includes certain elements?

Question

I am trying out Prolog for the first time and am having a little difficulty using lists.

Say I have a list of elements. I want to check that the list has the following elements:

All of: A1, A2, A3, A4, A5

One of: B1, B2, B3, B4

Two of: C1, C2, C3, C4, C5, C6

For example, [A1, A2, B2, C1, A3, A4, C4, A5] meets the requirements and [A2, A1, C1, B1, A3, A4] does not.

How would I got about writing something that returns Yes/True if a list meets the requirements and No/False otherwise? Similarly, how about writing something that returns the missing values from the list needed to meet the requirements?

Answer 1

You asked a lot of questions! Let me get you started with some predicates that solve most of your requirements.

First let's tackle the case of checking that all entries of one list are also in the other list:

subset([ ],_).
subset([H|T],List) :-
    member(H,List),
    subset(T,List).

This simple recursion makes use of the familiar member/2 predicate to verify each entry in the list specified by the first argument of subset/2 is also in the list specified by the second argument. [For simplicity I've assumed that entries of these list are distinct. A more elaborate version would be needed if we wanted to verify multiple instances of an entry of the first list are matched to at least that many instances in the second list.]

Okay, how about a check that (at least) one of a first list belongs also to the second list? Obviously this is a different predicate than the one above. Instead of all items in the first list, the goal is to be satisfied if there exists any one item in the first list that belongs to the second list.

intersects([H|_],List) :-
    member(H,List),
    !.
intersects([_|T],List) :-
    intersects(T,List).

This recursion fails if it reaches an empty list for the first argument, but succeeds if at any point before that a member of the first list is found that belongs to the second list. [This predicate would work fine even if multiple instances of an item occur in either list. However we'd need to refine the logic if we wanted check exactly one item of the first list belongs to the second list, and that would entail worrying about whether multiple instances are consistent with or counter to the exact count of one.]

What if we want to generalize this check, to verify (at least) N items of the first list are in the second one? The resulting predicate will require a third argument:

intersectsAtLeast(_,_,N) :- N <= 0, !.
intersectsAtLeast([H|T],L,N) :-
    member(H,L),
    !,
    M is N-1,
    intersectsAtLeast(T,L,M).
intersectsAtLeast([_|T],L,N) :-
    intersectsAtLeast(T,L,N).

This recursion works through the list, decrementing the third argument by one each time an item on the first list turns out to be in the second list as well, and succeeding once the count is reduced to 0 (or less). [Again the code here needs more work if the lists can have repetitions.]

Finally you ask about writing something that "returns the missing values" need to meet requirements. This is not well defined in the case of checking for one or more items on both lists, since a "missing value" might be any one of a number of possible items. In the special case where we asked for all the items on the first list to belong to the second list, the "missing values" can be determined (if any).

missingValues([ ],_,[ ]).
missingValues([H|T],L,K) :-
    member(H,L),
    !,
    missingValues(T,L,K).
missingValues([H|T],L,[H|K]) :-
    missingValues(T,L,K).

Here the recursion "moves" items from the input first list to the output "missing items" third list if and only if they do not appear in the second list.

One final note about your questions concerns notation. In Prolog variables are identifiers that start with a capital letter or an underscore, so the use of A1, A2, etc. as items on the list is heading for trouble if those are treated as "unknowns" rather than (as I assume you meant) distinct atoms (constants). Switching to lowercase letters would solve that.