# Trees as terms

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

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

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.

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
```

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),
nl,tab(Pos), % skip to position Pos
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.