6    Built-in Predicates

Solutions

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]

Solution 6.1

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

Solution 6.2

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).
distance( baden, basel, 83).
...

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.

Solution 6.3

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

Solution 6.4

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]

Solution 6.5