# 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).
```

Figure 4.2 Which are the paths through this tree?

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/2`2 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.