Module 17 Lab

As in last week’s lab, you should open two terminal windows, create a directory for your Prolog work and
cd
to it in both windows, and create a file calledlab6.pl
. 
Lists are almost as important in Prolog as they are in Haskell, and there is a similar syntax for defining them. The empty list is designated
[]
. The list whose first element isA
and remaining elements are the listB
is designated[AB]
. Note thatA
is a single element andB
is a list, just like in Haskell. So the notation[AB]
in Haskell terms isA:B
(except that in Haskell these variables would have to be lowercase). A list can also be made by just putting its elements between brackets separated by commas. Type[1,2,3,4]=[AB].
followed by Enter inswipl
. 
Prolog has lots of builtin list predicates. Type
member(X,[1,2,3,4]).
Hit semicolon until the goal fails, or type a to see all the ways this goal can be satisfied. Typemember(1,[AB]).
and hit semicolon several times before just hitting Enter. What is happening? 
One difference between Haskell and Prolog with regard to list syntax is that the concatenation operator can be used multiple times in Haskell, so
a:b:c:[]
is the list[a,b,c]
. In Prolog, this would be[a,b,c[]]
instead (or just[a,b,c]
, of course). But pattern matching with the concatenation operator in Prolog is just as powerful as it is in Haskell; for example[X1,X2,X3,X4T]
matches a list with at least four elements;X1
is instantiated to the first,X2
to second, and so forth, andT
is instantiated to the rest of the list after the fourth element. 
Lets make a predicate
size(L,N)
that counts how many elements are in a listL
. We know that the size of an empty list is zero:size([],0).
We also know that the size of a nonempty list is one more than the size of that list with its first element removed:size([_T],N) : size(T,M), N is M+1.
Note that the special infix predicateis
must be used to get Prolog to evaluate an arithmetic expression. Note thatM
here could be considered a “temporary variable” that is used to denote an intermediate result useful for computing our desired results. Type these rules intolab6.pl
, save the file, and consult it. Experiment to see how these rules work. Write tests for thesize
predicate. 
Note that the order in which things occur here is very important: if the second rule has its conjuncts reversed, there will be an instantiation error because
M
will not have a value whenM+1
is evaluated. Furthermore, one must keep in mind the order in which the inference engine tries to satisfy its goals. Notice too that we are using recursion in this predicate; we will use recursion to process lists frequently. Finally, Prolog has a builtin predicatelength
that works likesize
. 
Write rules in
lab6.pl
to implement a predicateend(L,X)
that places the last element of listL
inX
(in other words, the predicateend(L,X)
should be true whenX
is the last element ofL
). It fails for the empty list. There is a builtin predicate calledfail
(no arguments) that you can use in a rule to obtain this behavior. Also write tests for this predicate. Note: Prolog has a builtinlast
predicate that works likeend
. 
Write rules to implement the predicate
max(L,X)
whose first argument is a list and whose last argument is the maximum number in the list. The predicate should fail if the list is empty. There are also builtin numeric infix comparison operators<
and=<
for less than and less than or equal to. You may assume that the list contains only numbers. Write tests for this predicate. Prolog has the predicatesmin_list
,max_list
,sum_list
, andsort
builtin. 
Write rules to implement the predicate
evens(L,M)
where the first argument is a list of numbers and the second argument is all of the even numbers from the first list (in the same order that they appear in the original list). In Prolog, the predicateX is Y mod Z
to assert the result of a modular arithmetic operation. For example, the following should succeed:evens([1,2,3,4], [2,4]).
You will probably need to use the cut operator (!
) to stop this predicate from returning multiple answers when you query it using a variable. 
Write rules to implement the predicate
concatenate(A,B,C)
whereC
is the result of appendingA
andB
. Write tests for it. Prolog has a builtinappend
predicate, of course. 
Prolog is more relaxed about types than Haskell. In Haskell, a list must contain elements that are all the same type. In Prolog, a list can contain elements of any type, including other lists. Hence the list
[1,a,[b,[]],4]
is perfectly fine in Prolog. It helps to be able to distinguish the types of list elements. The builtin predicatelist(X)
does this, succeeding ifX
is a list and failing otherwise. 
Suppose that we wanted to represent binary trees like we did in the second Haskell lab. We could do this using lists as tuples because Haskell allows us to have multiple types in a list. For instance, we could designate
[empty]
to represent an empty tree and[node,X,L,R]
to represent a node with some valueX
and subtreesL
andR
. Here are Prolog rules that will generate binary search trees using that kind of data structure:% toplevel: invoke recursive insertion on an empty tree bst(L,T) : build_bst(L, [empty], T), !. % empty list: no tree modifications necessary build_bst([], T, T). % nonempty list: insert the head and recurse on the tail build_bst([XXS], T, TTT) : insert_bst(X, T, TT), build_bst(XS, TT, TTT). % empty tree: create new node insert_bst(V, [empty], [node,V,[empty],[empty]]). % binary node: insert into left or right subtree insert_bst(V, [node,X,L,R], [node,X,LL,R]) : V =< X, insert_bst(V,L,LL). insert_bst(V, [node,X,L,R], [node,X,L,RR]) : V > X, insert_bst(V,R,RR).
Test this code by comparing the results of running
bst([1,2,3],T).
andbst([3,2,1],T).

Write a rule
find(X,T)
that is true only ifX
is an element in the binary search treeT
. You can use the following rule to simplify testing:find_bst(X,L) : bst(L,T), find(X,T), !.
For instance,
find_bst(3, [1,3,5]).
should succeed whilefind_bst(4, [1,3,5]).
should fail. Note that there is no notion of “returning true” or “returning false” in Prolog; predicates may only either succeed or fail! Thus, you do not need to write any code to describe the “false” condition, only the true conditions. 
Write a rule
sorted(T,L)
that creates a sorted listL
of all items in a binary search treeT
. You can use the following rule to simplify testing:sorted_bst(L,S) : bst(L,T), sorted(T,S), !.
For instance,
sorted_bst([3,8,6,1,4,9],X).
should produce the resultX = [1,3,4,6,8,9]
. 
Write a rule
count_nodes(T,N)
that counts the number of nodesN
in a binary search treeT
.count_bst(L,N) : bst(L,T), count_nodes(T,N), !.
For instance,
count_bst([3,6,8],X)
should produce the resultX = 3
.Congratulations! You have just written an extremely complicated and much slower alternative implementation for the
size
orlength
predicates! :)However, you now have all the tools you need to implement the project for this module.
This lab was originally written by Dr. Chris Fox and expanded by Dr. Mike Lam.