Week 3: Exercises

1. Select

Implement this built-in predicate:

select(?X, ?XList, ?Y, ?YList)

True if XList and YList are identical except for a single element, which is X in XList and is Y in YList.

2. Permutation

Implement this built-in predicate:

permutation(?Xs, ?Ys)

True if Xs is a permutation of Ys.

3. Integer Ranges

Implement these two built-in predicates:

between(+Low, +High, ?Value)

True if all arguments are integers and Low ≤ Value ≤ High. This predicate can generate all values between Low and High.

numlist(+Low, +High, -List)

True if List is the list [Low, Low + 1, …, High].

4. Insertion Sort

Write a predicate that sorts a list of integers. Use an insertion sort.

5. Flatten

Write a predicate that can flatten a list of lists into a single-level list. For example, flatten([ [1, 2, 3], [4], [5, 6] ], L) will produce L = [1, 2, 3, 4, 5, 6].

6. Combining Digits

Write a predicate that can combine a list of decimal digits into an integer. For example, combine([2, 4, 6], N) will produce N = 246.

7. Graph Path

Consider a directed graph defined like this:

edge(a, b). edge(a, c). edge(b, d). edge(c, d).
edge(c, f). edge(d, e). edge(d, f). edge(f, a).

Write a predicate path(V, W, L) that is true if L is a path from vertex V to W. For example, path(a, e, [a, c, d, e]) is true. When given two vertices and an unbound path variable, the predicate should generate all paths in increasing order of length.