Week 2 - Tutorial Solutions

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:

2. 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(X, Y) :-
       parent(X, Y).
   ancestor(X, Z) :-
       parent(X, Y),
       ancestor(Y, Z).
   
   ?- ancestor(pam, X).
   X = bob ;
   X = ann ;
   X = pat ;
   X = jim ;
   false.

3. 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, and binds NewList to the list obtained by inserting Num into List so that the resulting list is still sorted in increasing order.

% Base case
insert(Num, [], [Num]).

% New node at front if less the first element
insert(Num, [Head|Tail], [Num, Head|Tail]) :-
    Num =< Head.

% Otherwise insert it in the tail
insert(Num, [Head|Tail], [Head|Tail1]) :-
    insert(Num, Tail, Tail1).

1. Write a predicate isort(List, NewList ) that takes a List of numbers in any order, and binds NewList to the list containing the same numbers sorted in increasing order. Hint: your predicate should call the insert/1 predicate from part 1.

Note: The notation insert/1 means the predicate insert, which takes 1 argument.

% Base case
isort([], []).

% Sort the tail then insert the head.
isort([Head|Tail], List) :-
    isort(Tail, Tail_Sorted),
    insert(Head, Tail_Sorted, List).

1. Write a predicate split(BigList,List1,List2) that 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?

% Base case 0: empty list
split([], [], []).

% Base case 1: list with one element
split([A], [A], []).

% First element in first list, second element in second list
% then split recursively
split([A, B|T], [A|R], [B|S]) :-
    split(T, R, S).

4. Write a predicate merge(Sort1, Sort2, Sort) that takes two lists Sort1 and Sort2 that are already sorted in increasing order, and binds Sort to a new list which combines the elements from Sort1 and Sort2 , and is sorted in increasing order.

% If one list is empty, return the other list
merge(X, [], X).
merge([], X, X).

% If first element of first list is smaller,
% it becomes the first element of the merged list
merge([A|R], [B|S], [A|T]) :-
    A =< B,
    merge(R, [B|S], T).

% If first element of second list is smaller,
% it becomes the first element of the merged list
merge([A|R], [B|S], [B|T]) :-
    A > B,
    merge([A|R], S, T).

Extra Challenge:

Write a predicate mergesort(List, NewList) 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.

% If one list is empty, return the other list
mergesort([], []).
mergesort([X], [X]).

% If the list has more than one element,
% split it into two lists of nearly equal length,
% sort the two smaller lists and merge them,
mergesort([A, B|T], S) :-
    split([A, B|T], L1, L2),
    mergesort(L1, S1),
    mergesort(L2, S2),
    merge(S1, S2, S).