Week 4: Exercises

1. Multiplication

Suppose that we represent natural numbers using structures: 0 = z, 1 = s(z), 2 = s(s(z)) and so on.

Write a predicate mul(A, B, C) that is true if A · B = C, where A, B, and C are natural numbers in this representation. Your predicate should work in all directions.

2. Integers

a) Invent a representation for integers using structures. Every possible integer should have a unique representation.

b) Write a predicate inc(I, J) that is true if J = I + 1, where I and J are integers in your representation.

c) Write a predicate less(I, J) that is true if I < J.

d) Write a predicate addi(I, J, K) that is true if I + J = K.

3. All Same

Write a predicate all_same(L) that is true if all elements of L are identical. Use maplist().

4. All Different

Write a predicate all_different(L) that is true if all elements of L are distinct. Use maplist().

5. Scalar Times Vector

Write a predicate mul(X, V, W) that is true if X · V = W, where X is a floating-point number and V and W are vectors represented as lists of floats. Use maplist().

6. Acute Angle

Write a predicate acute(V, W) that takes two vectors of dimension 2 or greater, represented as lists of floats. The predicate should succeed if the angle between the vectors is acute, i.e. less than 90 degrees.

7. Zip

Suppose that we use the operator / for representing pairs of values:

?- X = a / b.
X = a/b.

Write a predicate zip() that will zip two lists of items into a list of pairs:

?- zip([a, b, c], [d, e, f], L).
L = [a/d, b/e, c/f].

8. Writing maplist()

The predicate maplist(P, L, M) takes a predicate P of two arguments. Implement this version of maplist() using call().

9. Matrices

We can represent a matrix as a list of lists of floating-point numbers.

Write a predicate size(M, N) that is true if M is a square matrix with dimensions N x N.

Also write predicates that can calculate the following:

  1. the zero matrix of a given size

  2. the sum of two matrices

  3. the first column of a matrix (a vector)

  4. the identity matrix of a given size

  5. the transpose of a matrix

  6. the product of two matrices

All predicates should work in any direction.

10. Crosswords

Suppose that we'd like to fill in a 3 x 3 grid with letters so that every row and column contains one of these words:

AGE, AGO, CAN, CAR, NEW, RAN, ROW, WON

Write a Prolog predicate that can find all possible solutions.