All data in Prolog is represented as terms. Here are the kinds of terms we have learned about so far:
an atom, which is a string beginning with a lowercase
letter and containing letters, digits and '_'. Examples: abc,
joe, orange_tree.
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 variable, which begins with an uppercase letter and may contain letters, digits, and '_'.
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 resembles a linked list internally, 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 the predicates that we wrote in the lecture.
% is_empty(L) is true if L is the empty list. is_empty([]). % non_empty(L) is true if L is a non-empty list. non_empty([_ | _]). % first_elem(X, L) is true if X is the first element of L. first_elem(X, [X | _]). % last_elem(X, L) is true if X is the last element of L. last_elem(X, [X]). last_elem(X, [_ | L]) :- last_elem(X, L). % member(X, L) is true if X is any member of the list L. member(X, [X | _]). member(X, [_ | L]) :- member(X, L). % append(L, M, N) is true if we can append L and M to make N. % In other words, it's true if L + M = N, where + means list concatenation. append([], L, L). append([X | L], M, [X | N]) :- append(L, M, N).