This week's material is covered in the Bratko text in sections 2.1 Data objects, 2.2 Matching, 3.1 Representation of lists and 3.2 Some operations on lists.
Here are some more notes.
A single-line comment begins with % and extends to
the end of the line. Comments delimited with /* and */
can extend over multiple lines.
All data in Prolog is represented as terms. A term is any of these:
an atom, which may have either of these syntactic forms:
a string beginning with a lowercase letter and containing
letters, digits and '_'. Examples: abc, joe,
orange_tree.
a string consisting of punctuation characters. Examples: &&,
$$$, !@! .
an number, which can be either an integer (e.g. 23 or -589) or a floating-point number (e.g. 5.27981). Integers may be of arbitrary size.
a string beginning and ending with double-quote characters, e.g. "flower".
a variable, which begins with an uppercase letter and may contain letters, digits, and '_'.
a structure (compound term), which consists of a functor and zero or more components. The functor has the same syntax as an atom. The components are arbitrary terms. Examples:
point(3,4)seg(point(X, Y), point(4,2))date(1,july, X)
a list, which is a structure with a special syntax. A list contains zero or more comma-separated terms, enclosed in brackets:
[3, 4, 5] [A, 3, [B, C]] []
A Prolog list is a linked list, and has the corresponding performance characteristics: the head is directly accessible, and prepending a value is a constant-time operation.
A term specifying a list may optionally include a vertical bar (|). In this case, the element after the vertical bar is a list containing all remaining items. For example, all of the following are equivalent:
[3, 4, 5] [3 | [4, 5]] [3, 4 | [5]] [3, 4, 5 | []]
Here are some examples of recursive predicates on lists. (All of these are actually built into Prolog - see our library quick reference).
% member(X, L) is true if X is a member of L member(X, [X | _]). member(X, [_ | L]) :- member(X, L). % append(L1, L2, M) is true if M is the concatenation of L1 and L2 append([], L, L). append([X | L], M, [X | N]) :- append(L, M, N). % same_length(L, M) is true if L and M are lists of the same length same_length([], []). same_length([_ | L], [_ | M]) :- same_length(L, M). % select(X, L, M) is true if we can remove X from L to make M. % Equivalently, it is true if we can insert X anywhere in M to make L. select(X, [X | L], L). select(X, [Y | L], [Y | L2]) :- select(X, L, L2).
Ideally a Prolog predicate will run in all directions and will always terminate if the result set is finite. Unfortunately it's not always so easy to tell whether the predicate will terminate just by looking at it. Often in practice you will need to run it to see what happens.
The select implementation above works in more than
one direction:
?- select(X, [3, 4, 5], L). X = 3, L = [4, 5] ; X = 4, L = [3, 5] ; X = 5, L = [3, 4] ; false. ?- select(2, L, [3, 4]). L = [2, 3, 4] ; L = [3, 2, 4] ; L = [3, 4, 2] ; false.
Let's cleverly reimplement select using append:
select(X, L1, L2) :- append(A, [X | B], L1), append(A, B, L2).
Now the first query above still works, but the second hangs after finding all solutions:
?- select(2, L, [3, 4]). L = [2, 3, 4] ; L = [3, 2, 4] ; L = [3, 4, 2] ; (hang) ^CAction (h for help) ? abort % Execution Aborted ?-
Here is a trick that can often help a predicate terminate: add a goal
that uses the same_length predicate to express the
relationship between two list lengths. For example:
select(X, L1, L2) :- same_length(L1, [_ | L2]),
append(A, [X | B], L1), append(A, B, L2).
Now the query select(2,
L, [3,
4])
correctly finds all solutions and terminates.
The same_length
trick works because it adds a logically valid constraint that helps
limit Prolog's search. If you want to understand it in more detail,
turn on tracing and study how Prolog resolves the above query with
and without the same_length
goal.
Here are solutions to some of the optional exercises for this week:
Write a predicate second_last(X, L)
that is true if X is the next-to-last element of L.
second_last(X, [X, _]). second_last(X, [_ | L]) :- second_last(X, L).
Write a predicate next_to(X, Y, L) that
is true if elements X and Y appear in L, with Y immediately after X.
next_to(X, Y, L) :- append(_, [X, Y | _], L).
Write a predicate even_length(L) that
is true if the length of L is an even integer.
even_length([]). even_length([_, _ | L]) :- even_length(L).
Write a predicate longer(L, M) that
is true if L is longer than M.
longer([_ | _], []). longer([_ | L], [_ | M]) :- longer(L, M).
Write a predicate double_length(L, M)
that is true if L is twice as long as M.
double_length([], []). double_length([_, _ | L], [_ | M]) :- double_length(L, M).
Write a predicate reverse(L, M) that
is true if L and M
contain the same elements in reverse order.
reverse([], []).
reverse([X | L], M) :-
same_length([X | L], M), reverse(L, LR), append(LR, [X], M).Notes:
The call to same_length ensures that queries in
both directions will terminate:
?- reverse(L, [a, b, c]). L = [c, b, a]. ?- reverse([a, b, c], L). L = [c, b, a].
This implementation of reverse runs in O(N2),
since appending a single element to a list of length N takes O(N).
Later in the course we will see how to write a version of reverse
that runs in O(N).
Write a predicate all_same(L) that
is true if all elements of L are identical.
all_same([]). all_same([_]). all_same([X, X | L]) :- all_same([X | L]).
Write a predicate all_diff(L) that
is true if no two elements of L are identical.
% helper predicate % all_diff(X, L) is true if X is different from every element in L all_diff(_, []). all_diff(X, [Y | L]) :- dif(X, Y), all_diff(X, L). % main predicate all_diff([]). all_diff([X | L]) :- all_diff(X, L), all_diff(L).
Write a predicate select(X, L, M) that is true if
X can be removed from L to make M. Equivalently, select(X, L,
M) is true if X can be inserted anywhere in M to make L.
select(X, L, M) :- same_length(L, [_ | M]),
append(A, [X | B], L), append(A, B, M).Write a predicate select(X, L, Y, M)
that is true if L and M are identical except (possibly) for a single
element, which is X in L
and is Y in M.
sel(X, L, Y, M) :- same_length(L, M),
append(A, [X | B], L), append(A, [Y | B], M).