CSE 341 -- Practice Prolog Problems

November 20, 1995


Take a look at the definition of append below. Remind yourself how it works and feel free to use it in your answers to the problems below.
append([],List,List).
append([X|Xs],[Ys],[X|Zs]) :- 
     append(Xs,Ys,Zs).

  1. Define two predicates evenlength(List) and oddlength(List) so that they are true if their argument is a list of even or odd length respectively. For example, the list [a,b,c,d] is 'evenlength' and [a,b,c] is 'oddlength'.
    evenlength([]).
    oddlength([_]).
    evenlength([X|Xs]) :- oddlength(Xs).
    oddlength([Y|Ys]) :- evenlength(Ys).
    

  2. Define the relation reverse(List,ReversedList) that reverses lists. For example, reverse([a,b,c,d],[d,c,b,a]).

    reverse([],[]).
    reverse([Head|Tail],List) :- 
         reverse(Tail,ReversedTail),
         append(ReversedTail,[Head],List). 
    
  3. Define the predicate palindrome(List). A list is a palindrome if it reads the same in the forward and in the backward direction. For example, [m,a,d,a,m].

    palindrome(X) :- reverse(X,X).
    
    or
    
    palindrome([]).
    palindrome([_]).
    palindrome(List) :- 
         append([Head|Middle],[Head],List),
         palindrome(Middle).
    
  4. Define the relation max(X,Y,Max) so that Max is the greater of two numbers X and Y.
    max(X,Y,X) :- 
         X >= Y.
    max(X,Y,Y) :- 
         X < Y.
    

  5. Define the relation maxlist(List,Max) so that Max is the greatest number in the list of numbers List.
    maxlist([X],X).
    maxlist([X,Y|Tail],Max) :-
         maxlist([Y|Tail],MaxTail),
         max(Head,MaxTail,Max). 
    

  6. Define the relation sumlist(List,Sum) so that Sum is the sum of a given list of numbers List.
    sumlist([],0).
    sumlist([X|Tail],Sum) :-
         sumlist([Tail],SumTail),
         Sum is X + SumTail.