Week 2 - Your First Prolog Programs

Recursion in Prolog

Note: You probably won't get through all of these in one hour. That's ok, but the ones you don't finish, try doing them in your own time and see if you can work them out before we publish the solutions next week.

1. Given the following Prolog clauses:

female(pam).
female(liz).
female(pat).
female(ann).
male(tom).
male(bob).
male(jim).

parent(pam, bob).
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).

mother(Parent, Child) :- parent(Parent, Child), female(Parent).
father(Parent, Child) :- parent(Parent, Child), male(Parent).

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

sister(Sister, Sibling) :-
    parent(P, Sister),
    parent(P, Sibling),
    female(Sister),
    Sister \= Sibling.

Define the ancestor relation such that ancestor(X, Y) is true if X is an ancestor of Y. What is the expected output of the query:

ancestor(pam, X).

2. Write a prolog predicate insert(Num, List, NewList) that takes a number Num along with a list of numbers List which is already sorted in increasing order. NewList is the list obtained by inserting Num into List so that the resulting list is still sorted in increasing order. E.g.

insert(2, [1, 3], [1, 2, 3]).
insert(1, [], [1]).    

3. Write a predicate isort(List, NewList) where List a list of numbers in any order, and NewList is the list containing the same numbers sorted in increasing order. Hint: your predicate should call the insert/3 predicate from question 2.
   Note: The notation insert/1 means the predicate insert , which takes 1 argument.

isort([4, 7, 2, 1], [1, 2, 4, 7]).
isort([], []).

4. Write a predicate split(BigList, List1, List2) which takes a list BigList and divides the items into two smaller lists List1 and List2 , as evenly as possible (i.e. so that the number of items in List1 and List2 differs by no more that 1). Can it be done without measuring the length of the list?

?- split([1,2,3,4,5], X, Y).
X = [1, 3, 5],
Y = [2, 4]

5. Write a predicate merge(Sort1, Sort2, Sort) where Sort1 and Sort2 are already sorted lists, and Sort is the list which combines the elements from Sort1 and Sort2 , and is sorted in increasing order.

6. ?- merge([1, 5, 6, 9], [2, 5, 11], X).
   X = [1, 2, 5, 5, 6, 9, 11]
   

Extra Challenge

Write a predicate mergesort(List, SortedList) which has the same functionality as the isort/2 predicate from part 2 above, but uses the MergeSort algorithm. Hint: you will need to use the split/3 and merge/3 predicates from parts 3 and 4 above.