# A library of utility predicates

## Contents

# 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).
```