  EN → DE A-AA+ Sitemap Search

# 6    Built-in Predicates

## 6.1    Higher-order Predicates

Implement the following predicates:

``````abolish( F, A)
/* erases all predicates with the main functor F and the arity A */

filter( P, X, Y)
/* filters the list X into the list Y according to the predicate P */
``````

Examples:

``````pos( X) :- X > 0.
neg( X) :- X < 0.
?- filter( pos, [ 1, -1, 2, -2], Y).  ⇒  Y = [ 1, 2]
?- filter( neg, [ 1, -1, 2, -2], Y).  ⇒  Y = [ -1, -2]
``````

## 6.2    Memoization

Fibonacci numbers F(N) can be computed as follows:

``````fibo( 0, 0).
fibo( 1, 1).
fibo( N, F) :-
N > 1,
N1 is N-1,
N2 is N-2,
fibo( N1, F1),
fibo( N2, F2),
F is F1 + F2.
``````

This method is extremely inefficient because intermediate results are recomputed many times. Avoid this deficiency by storing the intermediate results using assert.

Note: Another efficient method is the iterative computation (implemented by recursion). To this purpose two additional arguments for F(N-1) and F(N-2) are introduced, F1 = F(N-1) and F2 = F(N-2). Consider the iterative implementation in a procedural language:

``````F2 = 0
F1 = 1
for k = 2 to N do:
Sum = F2 + F1
F2 = F1
F1 = Sum
return F1
``````

## 6.3    User Interaction

Write a program for interactive querying the distance between two cities:

``````?- d( City1, City2).
``````

Suppose that the distances are stored in a database, e.g. :

``````distance( zuerich, baden, 22).
...
``````

Take the symmetry of the distance relation into account. If a distance is not known, the system should not answer NO but it should request the distance from the user and store it for later usage.

The session could look like:

``````?- d( zuerich, baden).
The distance between zuerich and baden is 22 km.
?- d( zuerich, bern).
I don't know. Please tell me: 110
Thank you. I confirm: The distance between zuerich and bern is 110 km.
?- d( zuerich, bern).
The distance between zuerich and bern is 110 km.
``````

## 6.4    Counter

Implement a counter. A counter has a name and a value, and is manipulated using the following operations:

``````init( C, V)
/* The counter C is set up and has the value V. */

get( C, V)
/* Unifies the value of the counter C with V. */

inc( C)
/* Increases the value of C by 1. */

dec( C)
/* Decreases the value of C by 1. */

del( C)
/* The counter C is removed from the database. */
``````

Example.:

``````?- init( c, 0), inc( c), inc( c), get( c, V).
⇒  V = 2
``````

## 6.5    Transformation of Facts into List Arguments

Implement bagof und setof. The predicate bagof( X, P, B) computes B ("bag") as a list of elements X, that satisfy P(X) . Example:

``````a(4).
a(1).
a(5).
a(3).
a(4).
a(1).

?- bag_of( X, a(X), B).  ⇒  B = [4, 1, 5, 3, 4, 1]

?- bag_of( b(c,X), a(X), B).  ⇒  B = [[b(c, 4), b(c, 1), b(c, 5), b(c, 3), b(c, 4), b(c, 1)]

?- bag_of( X, (a(X), X>2), B).  ⇒  B = [4, 5, 3, 4]
``````

The list B can contain duplicate elements. The order of the elements is irrelevant.

The predicate setof(X, P, S) is similar to bagof, but the list S is a proper mathematical set without duplicate elements. Moreover, the list S is sorted according to the relation '<'. Example:

``````?- set_of( X, a(X), S).  ⇒  S = [1, 3, 4, 5]

?- set_of( X, (a(X), X>2), S).  ⇒  S = [[3, 4, 5]
``````