Trees as terms
4.1. Trees as terms#
Recall from Section 1.3 that complex Prolog terms like
can be viewed as a tree, with the functor
route acting as the root of (sub)trees, and
noroute as leaves (Figure 1.6). Conversely, trees can be represented by Prolog terms.
Draw the tree represented by the term
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]).
The principle of data abstraction prescribes to keep datastructures local to specific predicates such as
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_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
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/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