# 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]
```