I have defined multiple predicates that seem to share a common form

user_13603478 0
Viewed 100

All of these predicates are defined in pretty much the same way. The base case is defined for the empty list. For non-empty lists we unify in the head of the clause when a certain predicate holds, but do not unify if that predicate does not hold. These predicates look too similar for me to think it is a coincidence. Is there a name for this, or a defined abstraction?

intersect([],_,[]).
intersect(_,[],[]).
intersect([X|Xs],Ys,[X|Acc]) :-
    member(X,Ys),
    intersect(Xs,Ys,Acc).
intersect([X|Xs],Ys,Acc) :-
    \+ member(X,Ys),
    intersect(Xs,Ys,Acc).

without_duplicates([],[]).
without_duplicates([X|Xs],[X|Acc]) :- 
    \+ member(X,Acc),
    without_duplicates(Xs,Acc).
without_duplicates([X|Xs],Acc) :-
    member(X,Acc),
    without_duplicates(Xs,Acc).

difference([],_,[]).
difference([X|Xs],Ys,[X|Acc]) :-
    \+ member(X,Ys),
    difference(Xs,Ys,Acc).
difference([X|Xs],Ys,Acc) :-
    member(X,Ys),
    difference(Xs,Ys,Acc).

delete(_,[],[]).
delete(E,[X|Xs],[X|Ans]) :-
    E \= X,
    delete(E,Xs,Ans).
delete(E,[X|Xs],Ans) :-
    E = X,
    delete(E,Xs,Ans).
prolog
2 Answers

There is an abstraction for "keep elements in list for which condition holds". The names are inclide, exclude. There is a library for those in SWI-Prolog that you can use or copy. Your predicates intersect/3, difference/3, and delete/3 would look like this:

:- use_module(library(apply)).

intersect(L1, L2, L) :-
    include(member_in(L1), L2, L).

difference(L1, L2, L) :-
    exclude(member_in(L2), L1, L).

member_in(List, Member) :-
    memberchk(Member, List).

delete(E, L1, L) :-
    exclude(=(E), L1, L).

But please take a look at the implementation of include/3 and exclude/3, here: https://www.swi-prolog.org/pldoc/doc/_SWI_/library/apply.pl?show=src#include/3

Also in SWI-Prolog, in another library, there are versions of those predicates called intersection/3, subtract/3, delete/3:

Those are similar in spirit to your solutions.

Your next predicate, without_duplicates, cannot be re-written like that with include/3 or exclude/3. Your implementation doesn't work, either. Try even something easy, like:

?- without_duplicates([a,b], L).

What happens?

But yeah, it is not the same as the others. To implement it correctly, depending on whether you need the original order or not.

If you don't need to keep the initial order, you can simply sort; this removes duplicates. Like this:

?- sort(List_with_duplicates, No_duplicates).

If you want to keep the original order, you need to pass the accumulated list to the recursive call.

without_duplicates([], []).
without_duplicates([H|T], [H|Result]) :-
    without_duplicates_1(T, [H], Result).

without_duplicates_1([], _, []).
without_duplicates_1([H|T], Seen0, Result) :-
    (   memberchk(H, Seen0)
    ->  Seen =    Seen0 , Result =    Result0
    ;   Seen = [H|Seen0], Result = [H|Result0]
    ),
    without_duplicates_1(T, Seen, Result0).

You could get rid of one argument if you use a DCG:

without_duplicates([], []).
without_duplicates([H|T], [H|No_duplicates]) :-
    phrase(no_dups(T, [H]), No_duplicates).

no_dups([], _) --> [].
no_dups([H|T], Seen) -->
    { memberchk(H, Seen) },
    !,
    no_dups(T, Seen).
no_dups([H|T], Seen) -->
    [H],
    no_dups(T, [H|Seen]).
user_144119970

Well, these are the "while loops" of Prolog on the one hand, and the inductive definitions of mathematical logic on the other hand (See also: Logic Programming, Functional Programming, and Inductive Definitions, Lawrence C. Paulson, Andrew W. Smith, 2001), so it's not surprising to find them multiple times in a program - syntactically similar, with slight deviations.

In this case, you just have a binary decision - whether something is the case or not - and you "branch" (or rather, decide to not fail the body and press on with the selected clause) on that. The "guard" (the test which supplements the head unification), in this case member(X,Ys) or \+ member(X,Ys) is a binary decision (it also is exhaustive, i.e. covers the whole space of possible X)

intersect([X|Xs],Ys,[X|Acc]) :-   % if the head could unify with the goal
    member(X,Ys),                 % then additionally check that ("guard")
    (...action...).               % and then do something

intersect([X|Xs],Ys,Acc) :-       % if the head could unify with the goal
    \+ member(X,Ys),              % then additionally check that ("guard")
    (...action...).               % and then do something

Other applications may need the equivalent of a multiple-decision switch statement here, and so N>2 clauses may have to be written instead of 2.

foo(X) :-
   member(X,Set1),
    (...action...).

foo(X) :-
   member(X,Set2),
    (...action...).

foo(X) :-
   member(X,Set3),
    (...action...).

% inefficient pseudocode for the case where Set1, Set2, Set3
% do not cover the whole range of X. Such a predicate may or
% may not be necessary; the default behaviour would be "failure"
% of foo/1 if this clause does not exist:

foo(X) :-
   \+ (member(X,Set1);member(X,Set2);member(X,Set3)),
    (...action...).

Note:

  • Use memberchk/2 (which fails or succeeds-once) instead of member/2 (which fails or succeeds-and-then-tries-to-succeed-again-for-the-rest-of-the-set) to make the program deterministic in its decision whether member(X,L).
  • Similarly, "cut" after the clause guard to tell Prolog that if a guard of one clause succeeds, there is no point in trying the other clauses because they will all turn out false: member(X,Ys),!,...
  • Finally, use term comparison == and \== instead of unification = or unification failure \= for delete/3.
user_8844630
Related