Module 17 Lab

1. 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 called lab6.pl.

2. 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 is A and remaining elements are the list B is designated [A|B]. Note that A is a single element and B is a list, just like in Haskell. So the notation [A|B] in Haskell terms is A: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]=[A|B]. followed by Enter in swipl.

3. Prolog has lots of built-in 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. Type member(1,[A|B]). and hit semicolon several times before just hitting Enter. What is happening?

4. 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,X4|T] matches a list with at least four elements; X1 is instantiated to the first, X2 to second, and so forth, and T is instantiated to the rest of the list after the fourth element.

5. Lets make a predicate size(L,N) that counts how many elements are in a list L. We know that the size of an empty list is zero: size([],0). We also know that the size of a non-empty 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 predicate is must be used to get Prolog to evaluate an arithmetic expression. Note that M here could be considered a “temporary variable” that is used to denote an intermediate result useful for computing our desired results. Type these rules into lab6.pl, save the file, and consult it. Experiment to see how these rules work. Write tests for the size predicate.

6. 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 when M+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 built-in predicate length that works like size.

7. Write rules in lab6.pl to implement a predicate end(L,X) that places the last element of list L in X (in other words, the predicate end(L,X) should be true when X is the last element of L). It fails for the empty list. There is a built-in predicate called fail (no arguments) that you can use in a rule to obtain this behavior. Also write tests for this predicate. Note: Prolog has a built-in last predicate that works like end.

8. 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 built-in numeric in-fix 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 predicates min_list, max_list, sum_list, and sort built-in.

9. 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 predicate X 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.

10. Write rules to implement the predicate concatenate(A,B,C) where C is the result of appending A and B. Write tests for it. Prolog has a built-in append predicate, of course.

11. 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 built-in predicate list(X) does this, succeeding if X is a list and failing otherwise.

12. 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 value X and subtrees L and R. Here are Prolog rules that will generate binary search trees using that kind of data structure:

    % top-level: 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).
    
    % non-empty list: insert the head and recurse on the tail
    build_bst([X|XS], 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). and bst([3,2,1],T).

13. Write a rule find(X,T) that is true only if X is an element in the binary search tree T. 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 while find_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.

14. Write a rule sorted(T,L) that creates a sorted list L of all items in a binary search tree T. 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 result X = [1,3,4,6,8,9].

15. Write a rule count_nodes(T,N) that counts the number of nodes N in a binary search tree T.

    count_bst(L,N) :- bst(L,T), count_nodes(T,N), !.
    

    For instance, count_bst([3,6,8],X) should produce the result X = 3.

    Congratulations! You have just written an extremely complicated and much slower alternative implementation for the size or length 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.