Prolog Tutorial 5: Recursive Structures
James Power, 1997.
In this section we look at how recursion can be used with structures
to implement some common data structures.
Linked Lists
Even though lists are actually built in to Prolog (we'll be looking
at this in the next tutorial), we can implement them ourselves using
structures.
We'll suppose for the purpose of this discussion that we're dealing
with lists of numbers. Each node in the list will have two
components: its contents, and a reference to the next node in the
list. In addition we'll assume that the empty list is called
nil. Thus, if we use a two-pace structure called
node to represent a single node, a list containing the
numbers 2, 6 and 7 would look like:
node(2, node(6, node(7, nil)))
Note that the smallest possible list is nil, and every other
list will contain nil as the "next field" of the last
node. In list terminology, the first element is usually called the
head of the list, and the rest of the list is called the
tail. Thus the head of the above list is 2, and its
tail is the list node(6, node(7, nil))
Inserting an element
Suppose we want to write a predicate that adds a new element onto
the head of the list; we should end up with a new list in which the
input list is the tail. Thus we get:
% add_front(List,Elem,NewList) is true if NewList is List with Elem inserted at the beginning
add_front(List,Elem,NewList) :- NewList = node(Elem,List).
Adding the element at the end of the list takes a little more effort,
since we need to pass down through all the elements to find the last
one, and add it in there. There are two cases:
- The input list is empty, in which case we create a new list with
just one element
- The input list has one or more elements; i.e. it is of the form
node(Head,Tail). In this case we recursively add the element to
the tail Tail.
Thus our code looks like:
% add_back(List,Elem,NewList) is true if NewList is List with Elem inserted at the end
add_back(nil, Elem, NewList) :-
NewList = node(Elem,nil). % New list with 1 element
add_back(node(Hd,Tl), Elem, NewList) :-
add_back(Tl, Elem, NewTl), % Add Elem to the tail of the list
NewList = node(Hd,NewTl). % Answer is Hd along with the new tail
Note that we have used some of Prolog's pattern-matching power here,
since we expect it to choose between the two predicates based on
whether the input list looks like either nil or
node(H,T). No list can match both these patterns.
Save the above predicates and load them into Prolog; now try the
following queries to test that they work:
- add_front(nil, 5, L1), add_front(L1, 7, L2), add_front(L2, 8, L3).
- add_back(nil, 5, L1), add_back(L1, 7, L2), add_back(L2, 8, L3).
- add_front(nil, 5, L1), add_front(L1, 7, L2), add_back(L2, 8, L3).
Exercises
Write predicates to:
- get the first element in a list
- get the last element in a list
- sum all the elements in a list
- add an element to a list in order (that is, assuming the
original list was ordered, the new one will still be ordered).
Binary Trees
A binary tree will be like a list, except that each node will have
two links to other trees - one to the left subtree, and one to the
right.
Thus, if we had the following tree:
2
|
+--+--+
| |
1 6
|
+-----+-----+
| |
4 7
+-+-+
| |
3 5
we would represent it as:
node(2, node(1,nil,nil), node(6, node(4,node(3,nil,nil), node(5,nil,nil)), node(7,nil,nil))
Often a binary tree will be ordered so that for any given node, the
contents of its left-subtree will all be less than the current node,
and the contents of the right will be greater than it. The tree shown
above is ordered in this way.
Exercise
- Write a predicate tree_insert(Tree,Elem,NewTree) which is true if
NewTree is the tree you get by adding the element Elem to
the tree Tree so as to preserve its ordering. Remember that
there will now be three cases:
- If the tree is empty, add the element at the root
- If the tree isn't empty, and Elem is less than the element
stored at the current node, then add Elem to the left subtree
- If the tree isn't empty, and Elem is greater than the element
stored at the current node, then add Elem to the right subtree
Try running the following queries:
- tree_insert(nil,4,T1), tree_insert(T1,5,T2),
tree_insert(T2,2,T3), tree_insert(T3,7,T4).
- tree_insert(nil,7,T1), tree_insert(T1,5,T2),
tree_insert(T2,4,T3), tree_insert(T3,5,T4).
- tree_insert(nil,2,T1), tree_insert(T1,4,T2),
tree_insert(T2,5,T3), tree_insert(T3,7,T4).
Notice how lop-sided the last tree is - clearly the structure of the
tree depends on the sequence in which we insert its elements...
- Write a predicate that calls write/1 for each element
stored on the tree, so that it prints out all elements in order
- Write a predicate that gets the sum of all the elements on the
tree
- Write a program that gets the height of the tree; i.e. the
maximum length of any path from the root to a leaf.
Written by James Power
Released under the GNU Free Documentation License
Last revised: 22 Oct 2006