10.2. A library of utility predicates

What follows is a small collection of predicates that are used by various programs throughout the book.

Lists and sets

We start with a couple of simple list predicates.

% element(X,Ys) <- X is an element of the list Ys
element(X,[X|Ys]).
element(X,[Y|Ys]):-
    element(X,Ys).

% append(Xs,Ys,Zs) <- list Zs is Xs followed by Ys
append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]):-
    append(Xs,Ys,Zs).

% remove_one(X,Ys,Zs) <- Zs is list Ys minus
%                        one occurrence of X
remove_one(X,[X|Ys],Ys).
remove_one(X,[Y|Ys],[Y|Zs]):-
    remove_one(X,Ys,Zs).

The difference between lists and sets is that the order of elements in a set is not important. Thus, a subset is different from a sublist. The predicate proper_subset/2 works only if the first argument is a list without duplicates!

% subset(Xs,Ys) <- every element of Xs occurs in Ys
subset([],Ys).
subset([X|Xs],Ys):-
    element(X,Ys),
    subset(Xs,Ys).

% proper_subset(Xs,Ys) <- Xs is a subset of Ys, and Ys
%                         has more elements than Xs
proper_subset([],Ys):-
    Ys \= [].
proper_subset([X|Xs],Ys):-
    remove_one(X,Ys,Ys1),
    proper_subset(Xs,Ys1).

The following three predicates use syntactic identity rather than unification, which is useful for lists containing variables.

var_element(X,[Y|Ys]):-
    X == Y.  % syntactic identity
var_element(X,[Y|Ys]):-
    var_element(X,Ys).

var_remove_one(X,[Y|Ys],Ys):-
    X == Y.  % syntactic identity
var_remove_one(X,[Y|Ys],[Y|Zs]):-
    var_remove_one(X,Ys,Zs).

var_proper_subset([],Ys):-
    Ys \= [].
var_proper_subset([X|Xs],Ys):-
    var_remove_one(X,Ys,Zs),
    var_proper_subset(Xs,Zs).

Conjunctions and disjunctions

Conjunctions and disjunctions are recursive datastructures, just like lists. However, whereas a single-element list such [1] is a complex term .(1,[]), a single-element conjunction or disjunction is a simple term. Therefore, each of the following predicates needs an extra clause for the single-element case. Note that true is the empty conjunction, while false represents the empty disjunction.

disj_element(X,X):-          % single-element disjunction
    not X=false,
    not X=(One;TheOther).
disj_element(X,(X;Ys)).
disj_element(X,(Y;Ys)):-
    disj_element(X,Ys).

conj_append(true,Ys,Ys).
conj_append(X,Ys,(X,Ys)):-   % single-element conjunction
    not X=true,
    not X=(One,TheOther).
conj_append((X,Xs),Ys,(X,Zs)):-
    conj_append(Xs,Ys,Zs).

disj_append(false,Ys,Ys).
disj_append(X,Ys,(X;Ys)):-   % single-element disjunction
    not X=false,
    not X=(One;TheOther).
disj_append((X;Xs),Ys,(X;Zs)):-
    disj_append(Xs,Ys,Zs).

conj_remove_one(X,X,true):-  % single-element conjunction
    not X=true,
    not X=(One,TheOther).
conj_remove_one(X,(X,Ys),Ys).
conj_remove_one(X,(Y,Ys),(Y,Zs)):-
    conj_remove_one(X,Ys,Zs).

Preventing variables from getting instantiated

Whenever Prolog reads a clause from its internal database, fresh copies of the variables in the clause are created. When a meta-interpreter uses an internal list of clauses, this is desirable as well. The predicate copy_term/2 uses the internal database to create a fresh copy of any term. copy_element/2 uses copy_term/2 to create a fresh copy of an item in a list.

% copy_term(Old,New) <- New is a copy of Old
%                       with new variables
copy_term(Old,New):-
    asserta('$copy'(Old)),
    retract('$copy'(New)),!.
copy_term(Old,New):-  % in case Old and New don't unify
    retract('$copy'(Old)),
    !,fail.

% copy_element(X,L) <- X is an element of L
%                      with new variables
copy_element(X,Ys):-
    element(X1,Ys),
    copy_term(X1,X).

try/1 is a meta-predicate which tests whether a goal succeeds, without returning an answer-substitution. This is achieved by taking advantage of the difference between negation as failure and logical negation.

% try(Goal) <- Goal succeeds, but variables
%              don't get instantiated
try(Goal):-
    not not Goal.

Various

The remaining predicates speak for themselves.

% variant of setof/3 which succeeds with the empty list
% if no solutions can be found
setof0(X,G,L):-
    setof(X,G,L),!.
setof0(X,G,[]).

% same_predicate(L1,L2) <- literals L1 and L2 have
%                          the same predicate and arity
same_predicate(L1,L2):-
    functor(L1,P,N),
    functor(L2,P,N).