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 lab17.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 X and remaining elements are the list Xs is designated [X|Xs]. Note that X is a single element and Xs is a list, just like in Haskell. So the notation [X|Xs] in Prolog is equivalent to X:Xs in Haskell (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. Execute the query [1,2,3,4]=[X|Xs]. in swipl. What is the result?

3. Prolog has lots of built-in list predicates. Type member(X,[1,2,3,4]). Hit semicolon until the goal fails. Type member(1,[X|Xs]). 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|Xs] matches a list with at least four elements; X1 is instantiated to the first, X2 to second, and so forth, and Xs is instantiated to the rest of the list after the fourth element.

5. Lets make a predicate size(L,N) that counts how many (N) 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([_|Xs], N) :- size(Xs, XsN), N is XsN + 1. Note that the special infix predicate is must be used to get Prolog to evaluate an arithmetic expression. Note that XsN 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 lab17.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 XsN will not have a value when XsN+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 lab17.pl to implement a predicate end(L, E) that places the last element of list L in E (in other words, the predicate end(L, E) should be true when E 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, M) 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). For example, the following should succeed: evens([1,2,3,4], [2,4]). Note that in Prolog, the predicate X is Y mod Z to assert the result of a modular arithmetic operation. 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(L1, L2, L) where L is the result of appending L1 and L2. (Hint: look back at the solution for myConcat from the Module 9 lab in Haskell for inspiration regarding the general approach.) Write tests for it. Prolog also has a built-in append predicate that you can use in the project if you don’t get this one working.

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 can do this using lists as tuples because Prolog 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(List, Tree) :- build_bst(List, [empty], Tree), !.
    
    % empty list: no tree modifications necessary
    build_bst([], Tree, Tree).
    
    % non-empty list: insert the head and recurse on the tail
    build_bst([X|Xs], CurrentTree, NewTree) :-
        insert_bst(X, CurrentTree, TmpTree),
        build_bst(Xs, TmpTree, NewTree).
    
    % empty tree: create new node for value
    insert_bst(V, [empty], [node,V,[empty],[empty]]).
    
    % binary node: insert value into left or right subtree (ignore if equal)
    insert_bst(V, [node,V,L,R], [node,V,L,R]).
    insert_bst(V, [node,X,L,R], [node,X,NewL,R]) :- V < X, insert_bst(V, L, NewL).
    insert_bst(V, [node,X,L,R], [node,X,L,NewR]) :- V > X, insert_bst(V, R, NewR).
    

    Test this code by comparing the results of running bst([1,2,3], T). and bst([3,2,1], T). If swipl abbreviates the output (e.g., [node|...]), you can append ; true to the query to cause it to pause after the solution, and then you can press the w (write) key to show the full solution.

13. Write a rule find(Val, Tree) that is true only if Val is an element in the binary search tree Tree. You can use the following rule to simplify testing:

    find_bst(Val, List) :- bst(List, Tree), find(Val, Tree), !.
    

    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 in general need to describe the “false” conditions (except in the empty-tree base case), only the true conditions.

14. Write a rule sorted(Tree, List) that creates a sorted list List of all items in a binary search tree Tree. You can use the following rule to simplify testing:

    sorted_bst(List, SortedList) :- bst(List, Tree), sorted(Tree, SortedList), !.
    

    For instance, sorted_bst([3,8,6,1,4,9],X). should produce the result X = [1,3,4,6,8,9]. Note that if the original list contains more than one of a particular element, only one will appear in the sorted list because the binary search tree does not store duplicates.

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

    count_bst(List, Count) :- bst(List, Tree), count_nodes(Tree, Count), !.
    

    For instance, count_bst([3,6,8],X) should produce the result X = 3. Note that if the original list contains duplicates, they will not be counted.

    Congratulations! You have just written an extremely complicated and much slower alternative implementation for the length and sort built-in predicates! :)

    However, you now also have all the tools you need to implement the project for this module. Good luck!

This lab was originally written by Dr. Chris Fox and expanded by Dr. Mike Lam.