Data & computation · Lesson 23 of 43

Structures & trees

Compound terms as records, and a binary search tree from scratch.

Compound terms are Prolog's records. Pick a functor and put your fields in the arguments:

person(name(ada, lovelace), born(1815), field(mathematics))

There are no declarations, you just write the term. Unification pulls out the pieces you ask for:

person(name(ada, lovelace), born(1815)).
person(name(alan, turing), born(1912)).
person(name(grace, hopper), born(1906)).

?- person(name(First, turing), born(Year))

?- person(name(Given, _), born(Y)), Y < 1910

Taking terms apart

Four built-in predicates inspect and build terms generically:

?- functor(point(3, 4), Name, Arity)

?- arg(2, point(3, 4), X)

?- point(3, 4) =.. List

?- T =.. [rect, 2, 5]

?- functor(T, pair, 2)

?- copy_term(f(X, Y, X), Copy)

=.. ("univ") converts between a term and a list [Functor | Arguments]. It lets a program construct goals and data at run time.

A binary search tree

Define a tree as either nil (empty) or t(Left, Value, Right). Every value in the left subtree is smaller than the node, every value in the right is larger. Inserting walks down the tree:

% insert(Tree, X, NewTree)
insert(nil, X, t(nil, X, nil)).
insert(t(L, V, R), X, t(L1, V, R)) :- X < V, insert(L, X, L1).
insert(t(L, V, R), X, t(L, V, R1)) :- X > V, insert(R, X, R1).
insert(t(L, V, R), V, t(L, V, R)).                     % already present

% in_order(Tree, Sorted)
in_order(nil, []).
in_order(t(L, V, R), Xs) :-
    in_order(L, Ls), in_order(R, Rs),
    append(Ls, [V|Rs], Xs).

% build a tree from a list
list_to_tree(List, Tree) :- foldl([X, T0, T]>>insert(T0, X, T), List, nil, Tree).

?- insert(nil, 5, T1), insert(T1, 3, T2), insert(T2, 8, T3)

?- list_to_tree([5, 3, 8, 1, 4, 7, 9], T)

?- list_to_tree([5, 3, 8, 1, 4, 7, 9, 3], T), in_order(T, Sorted)

Because in_order is a relation, you can also run it backwards and ask for a tree with a given traversal:

?- in_order(t(nil, 1, t(nil, 2, nil)), L)

Exercise: Size of a tree

Using the nil / t(Left, Value, Right) representation, write tree_size(Tree, N): the number of values stored in the tree.