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).
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),
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
PredicatewithArityasPredicate/Arity. This is because predicates with different arity are different predicates, even if they share the same predicate name.