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.

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).
../../../_images/image0081.svg

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),
    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/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.