How to correctly write an implication in implication with prolog?

Question

I am trying to write a predicate, that will be true if and only then if list D contains elements from list A, the number of times those elements are in list A. For example -

D[1, 5, 5, 3]; A[4, 6, 1, 0, 5, 3, 5]

will be true

D[1, 5, 5, 3]; A[4, 6, 1, 0, 5, 3, 5, 5]

will be false, because D has 5 only two times, but A has 5 three times. And I am trying to do this with implications. My code snippet is as fallows-

sub_third(_, []) :-
    true.

sub_third(D, [H|T]) :-
    member(H, D) -> 
        select(H, D, D_new), sub_third(D_new, T) ; 
        false.

third(_, [], _) :-
    true.

third(D, [H|T], A) :-   
    (\+member(H, D) -> 
        select(H, A, A_new), third(D, T, A_new) ; 
        third(D, T, A)) -> 
            (sub_third(D, A_new);
            false).

Basically what I am doing here is passing the 'third' predicate list D and twice list A. With first implementation I am trying to remove all the elements from second A list, that are not found in the first A list (if H element exist in list D, then call the call recursive with next T elements and make no changes, but if H is not found in D list, then remove it from second A list and call recursive again, but with modified A list). When there are no more T elements, list A should contain only the same elements as list D and then with sub_third predicate find out, if all the elements are the same count. Sub_third works fine, so I think that mistake should be somewhere within the implications since I am not that familiar with them.

P.S. member function checks if element is a member of a list and select function takes in an element and list, then makes third list from the first list with removed given element. (that's how I used it here)

Isabelle Newbie Isabelle Newbie · Accepted Answer · 2016-11-23T14:15:29

You should try to find clearer names for your predicates. Even if you know what sub_third is supposed to mean, we don't. That makes it harder to understand and adapt your code.

Your basic idea of using select/3 is good, but you have not decomposed the problem properly. Try computing the difference between your lists first, and then checking the extra property that it does not contain any unwanted elements:

% list_subtract(Xs, Ys, Zs) is true if Zs is a list obtained by removing one
% occurrence of each element of Ys from Zs. False if there are elements in
% Ys that have no corresponding occurrence in Xs.
list_subtract(Xs, [], Xs).
list_subtract(Xs, [Y|Ys], Zs) :-
    select(Y, Xs, Xs1),
    list_subtract(Xs1, Ys, Zs).

% tests
:- list_subtract([4, 6, 1, 0, 5, 3, 5], [1, 5, 5, 3], Zs), Zs = [4, 6, 0].
:- list_subtract([4, 6, 1, 0, 5, 3, 5, 5], [1, 5, 5, 3], Zs), Zs = [4, 6, 0, 5].

% list_subtract_without_rest(Xs, Ys, Zs) is true if Ys can be subtracted
% from Xs in the sense of the list_subtract/3 predicate, and the remaining
% difference Zs does not contain any elements of Ys.
list_subtract_without_rest(Xs, Ys, Zs) :-
    list_subtract(Xs, Ys, Zs),
    \+ (member(Z, Zs), member(Z, Ys)).

% tests
:- list_subtract_without_rest([4, 6, 1, 0, 5, 3, 5], [1, 5, 5, 3], _).
:- \+ list_subtract_without_rest([4, 6, 1, 0, 5, 3, 5, 5], [1, 5, 5, 3], _).

How to correctly write an implication in implication with prolog?

1 Answers