# 4.1. Trees as terms#

Recall from Section 1.3 that complex Prolog terms like

route(tottenham_court_road,route(leicester_square,noroute))


can be viewed as a tree, with the functor route acting as the root of (sub)trees, and tottenham_court_road, leicester_square, and noroute as leaves (Figure 1.6). Conversely, trees can be represented by Prolog terms.

Exercise 4.1 #

Draw the tree represented by the term n1(n2(n4),n3(n5,n6)).

A tree is traversed by first visiting its root, and then recursively traversing all of its subtrees. A list of subtrees is obtained by decomposing the complex term by means of the =.. predicate (see Section 3.7):

% term_tree(T,R,S) <- term T represents a tree with root R
%                     and list of subtrees S
term_tree(Tree,Root,Subtrees):-
Tree=..[Root|Subtrees].

% term_root(T,R) <- R is the root of tree T
term_root(Tree,Root):-
term_tree(Tree,Root,_S).

% term_subtree(T,S) <- S is a subtree of tree T
term_subtree(Tree,Subtree):-
term_tree(Tree,_R,S),
member(Subtree,S).

/** <examples>
?- term_tree(n1(n2(n4,n5(n7),n6),n3(n8,n9(n10))),Root,Subtree).
?- term_tree(T,n1,[n2(n3),n4]).
*/


By means of these simple predicates, we can write a program for finding arcs and paths in a tree. Paths are represented as lists of nodes, and an arc is simply a path consisting of two nodes:

% term_arc(T,A) <- T is a tree, and A is an arc in T
term_arc(Tree,[Root,SR]):-             % Arc from Root to Subtree
term_root(Tree,Root),
term_subtree(Tree,Subtree),
term_root(Subtree,SR).

term_arc(Tree,Arc):-                   % Arc in Subtree
term_subtree(Tree,Subtree),
term_arc(Subtree,Arc).

% term_path(T,P) <- T is a tree, and P is a path in T
term_path(Tree,Arc):-                  % consisting of one arc
term_arc(Tree,Arc).

term_path(Tree,[Node1,Node2|Nodes]):-  % several arcs
term_arc(Tree,[Node1,Node2]),
term_path(Tree,[Node2|Nodes]).


Data abstraction#

The principle of data abstraction prescribes to keep datastructures local to specific predicates such as term_tree, term_root and term_subtree, and to access the datastructures only through these predicates. The main advantage of this design principle is modularity: if we choose to change the representation of a tree, we just have to modify these specific predicates, but the predicates which call them need not be changed. In contrast, if we unfold term_tree, term_root and term_subtree into the definition of term_arc, we get the following piece of code:

term_arc(Tree,[Root,R]):-
Tree=..[Root|Subtrees].
element(Subtree,Subtrees),
Subtree=..[R|S].
term_arc(Tree,Arc):-
Tree=..[Root|Subtrees].
element(Subtree,Subtrees),
term_arc(Subtree,Arc).


This program fragment is badly designed, because term_arc explicitly mentions the way trees are represented by Prolog terms. Consequently, if we change this representation, term_arc needs to be changed as well. This illustrates that the design of good datastructures is as important in Prolog as it is in any other programming language.

Exercise 4.2 #

Give a term Tree, such that it contains the tree of Exercise 4.1, and such that Path=[n1,n2,n7,n8] is an answer to the query

?-term_path(Tree,Path).


Consider the tree in Figure 4.2. The following query lists all the paths in this tree:

?-term_path(n1(n2(n4,n5(n7),n6),n3(n8,n9(n10))),Path).
Path = [n1,n2];
Path = [n1,n3];
Path = [n2,n4];
Path = [n2,n5];
Path = [n2,n6];
Path = [n5,n7];
Path = [n3,n8];
Path = [n3,n9];
Path = [n9,n10];
Path = [n1,n2,n4];
Path = [n1,n2,n5];
Path = [n1,n2,n6];
Path = [n1,n2,n5,n7];
Path = [n1,n3,n8];
Path = [n1,n3,n9];
Path = [n1,n3,n9,n10];
Path = [n2,n5,n7];
Path = [n3,n9,n10];
No more solutions


Exercise 4.3 #

Explain the order in which these paths are found.

It would be convenient to have a program for printing Prolog terms which represent trees in a tree-like way. The nicest way to do this is to print from the root down; however, this requires a rather elaborate program1. A reasonable alternative is to print the tree rotated at 90 degrees, from the root to the right. A program to do this is given below.

term_write(Tree):-
term_write(0,Tree),nl.

% write a Tree at position Pos
term_write(Pos,Tree):-
term_tree(Tree,Root,Subtrees),   % decompose Tree
term_write_node(Pos,Pos2,Root),  % write Root
term_writes(Pos2,Subtrees).      % new position

% write a list of trees at position Pos
term_writes(Pos,[]).
term_writes(Pos,[Tree]):-!,          % no newline here
term_write(Pos,Tree).
term_writes(Pos,[Tree|Subtrees]):-
term_write(Pos,Tree),
term_writes(Pos,Subtrees).

% write a Node from Begin to End
term_write_node(Begin,End,Node):-
name(Node,L),length(L,N),        % N is length of Nodename
End is Begin+10,
N1 is End-Begin-N,               % N1 is length of line
write_line(N1),
write(Node).

% write a line of given length
write_line(0).
write_line(N):-
N>0,N1 is N-1,
write('-'),
write_line(N1).


name/22 is a built-in predicate, converting an atom into a list of ASCII-codes. In combination with length/2, it is used to determine the number of characters in an atom. The query ?-term_write(n1(n2(n4,n5(n7),n6),n3(n8,n9(n10)))) displays the tree as follows:

--------n1--------n2--------n4
--------n5--------n7
--------n6
--------n3--------n8
--------n9-------n10


1

Such a program should perform breadth-first search; see Exercise 5.2.

2

From now on, we denote a Predicate with Arity as Predicate/Arity. This is because predicates with different arity are different predicates, even if they share the same predicate name.