Exercises (Prolog)

  1. A predicate length/2 describing the length of a list can be defined as follows. 
      length(0,[]).
  length(N,[_|L]) :- length(M,L), N is M+1.
    Please define predicates member/2, fac/2, fib/2, and gcd/3 analogously.

  2. Suppose predicates parent/2, female/1 i male/1 with the obvious interpretation are given.
    Please define predicates child/2, mother/2, sister/2, has_a_child/1, grandparent/2, and predecessor/2.

  3. Suppose the following predicate f/2 is given. 
     f(1,one).
 f(s(1),two).
 f(s(s(1)),three).
 f(s(s(s(X))),N) :- f(X,N).
    How does Prolog answer to the following questions?

    1. f(s(1),A)?
    2. f(s(s(1)),two)?
    3. f(s(s(s(s(s(s(1)))))),C)?
    4. f(D,three)?

  4. Please define a predicate latin/2, which transforms Latin numbers into arabic numbers. Latin numbers are represented by ordinary lists,
    for example [x,l,v,i,i] denotes 47. You can assume that the Latin number is correct.

  5. Assume the following predicates are given. 
     q1(X,Y) :- p(X,Y).                q2(X,Y) :- p(X,Z), q2(Z,Y).
 q1(X,Y) :- p(X,Z), q1(Z,Y).       q2(X,Y) :- p(X,Y).  

 q3(X,Y) :- p(X,Y).                q4(X,Y) :- q4(X,Z), p(Z,Y).  
 q3(X,Y) :- q3(X,Z), p(Z,Y).       q4(X,Y) :- p(X,Y). 
    
 p(tom,bob).
 p(tom,liz).
 p(bob,ann).      
 p(bob,pat).     
 p(pat,jim).
    Using answer trees please show how Prolog answers to the following questions: ?-qi(tom,pat). and ?-qi(liz,jim) for i = 1, ... 4.

  6. Please define the following predicates for lists.

    1. last(X,L), which is fulfilled if X is the last element of L.

    2. delete(X,L1,L2), which is fulfilled if L2 is the list L1 without the element X.

    3. delete(L1,L2), which is fulfilled if L2 is the list L1 without L1's last three elements.

    4. reverse(L1,L2), which is fulfilled if L2 is the list L2 in reversed order.

    5. evenlength(L) and oddlength(L), which are fulfilled if the length of L is even and odd, respectively.

    6. shift(L1,L2), which is fulfilled if L2 the list L1 after one rotation to left.
      Example: 
       ?- shift([1,2,3,4,5],L).
 L = [2,3,4,5,1]
    7. quadrat(L1,L2), which is fulfilled if L2 contains the squares of the elements of L1.
      Example: 
       ?- quadrat([1,2,3,4,5],L).
 L = [1,4,9,16,25]
    8. combine(L1,L2,L3), which is fulfilled if L3 contains the pairs of the elements of L1 and L2.
      Example: 
       ?- combine([1,2,3,4],[a,b,c,d],L).
 L = [[1,a],[2,b],[3,c],[4,d]]
    9. palindrom(L), which is fulfilled if L contains a palindrom.
      Examples: 
       ?- palindrom([a,b,c]).
 no
 ?- palindrom([a,b,c,d,c,b,a]).
 yes
    10. p(X,L,Y,Z), which is fulfilled if Y is the predecessor of X in L and Z is the successor of X in L.
      Example: 
       ?- p(3,[1,2,3,4,5],Y,Z).
 Y = 2, Z = 4
    11. q(X,L1,L2), which is fulfilled if L2 is the beginning of the list L1 up to the (first) double occurence of element X.
      Example: 
       ?- q(3,[1,2,3,3,1,2,4],Z).
 Z = [1,2,3,3]
  7. Assume the following definition of the predicate append is given. 
      append([X|L1], L2, [X|L3]) :- append(L1, L2, L3).
  append([], L, L).
    Using answer trees please show how Prolog answers to the questions 
     ?- append(X, [3,4], [2,3,4]).
  8. Please define the following predicates for lists.

    1. nth(N,L,X), which is fulfilled if X is the N-th element in the list L.

    2. ordered(L), which is fulfilled if list L is ordered.

    3. mergesort(L1,L2), which is fulfilled if L2 is the ordered version of the list L1. The predicate should simulate algorithm mergesort.

  9. Please define a predicate permutation(L1,L2), which is fulfilled if the list L2 is a permuation of L1.
    (Using ";" it should be possible to enumerate all permutations of L1.)

  10. A binary tree T is either empty - represented by the term nil - or consists of an element X (the root element) and two subtrees L and P - represented by the term node(X,L,P).
    Please define the following predicates for binary trees.

    1. size(T,N), which is fulfilled if N is the number of elements of tree D.

    2. search(T,X), which is fulfilled if X appears in tree T.

    3. max(T,X), which is fulfilled if X is the greatest element of tree T.

    4. times(N,T1,T2), which is fulfilled if D2 is the tree D1 in which each element has been multiplied with N.

    5. preorder(T,L), which is fulfilled if L is the list of D's elements in preorder.

  11. Please define a predicate route(Place1,Place2,Day,Route) finding connections based on a timetable.
    The timetable is given by a predicate timetable(Place1,Place2,List_of_flights), where List_of_Flights is a flight list from Place1 to Place2.
    Each flight is a list [Departure_time,Arrival_time,Flight_number,List_of_days].
    Example timetable: 
        timetable(edinburgh,london,
       [ [ 9:40, 10:50, ba4733, alldays],
         [13:40, 14:50, ba4773, alldays],
         [19:40, 20:50, ba4833, [mo,tu,we,th,fr,su]] ]).
     
    timetable(london, edinburgh,
       [ [ 9:40, 10:50, ba4732, alldays],
         [13:40, 14:50, ba4752, alldays],
         [18:40, 19:50, ba4822, [mo,tu,we,th,fr]] ]).
     
    timetable(london,ljubljana,
       [ [13:20, 16:20, ju201, [fr]],
         [13:20, 16:20, ju213, [su]] ]).
     
    timetable(ljubljana, zurich,
       [ [11:30, 12:40, ju322, [tu,th]] ]).
   
    timetable(zurich, london,
       [ [ 9:00,  9:40, ba613, [mo,tu,we,th,fr,sa]],
         [16:10, 16:55, sr806, [mo,th,we,th,fr,su]] ]).
    A connection Route from Place1 to Place2 is a list of flights PlaceA-PlaceB:Flight_number:Departure_time such that

    1. PlaceA in the first element of Route is Place1.
    2. PlaceB in the last element of Route is Place2.
    3. all flights in Route take place the same day.
    4. Between all flights there is enough transfer time, let's say 45 minutes.

    Example: 
         ?- route(ljubljana,edinburgh,th,Route).
     Route = [ljubljana-zurich:ju322:11:30, zurich-london:sr806:16:10, london-edinburgh:ba4822:18:40].
  12. Please give the Answer trees for the following queries. Which answers gives Prolog? 
    1.  s(X) :- p(X), r(X).
 s(X) :- q(X).
 p(a).   q(a).   r(a).
 p(b).   q(c).   r(b).                        ?- s(X).
    2.  q(X) :- p(X), r(X).
 p(a).
 r(a).
 r(f(Y)) :- r(Y).                             ?- r(Z).  and  ?- q(Z).
    3.  p(X,Z) :- q(X,Y), p(Y,Z).
 p(X,X).
 q(a,b).                                      ?- p(X,b).
  13. Using Answer trees please show, how Prolog answers to the following queries. 
    1.  p(x) :- a(x).
 p(x) :- b(x), c(x), !, d(x).
 p(x) :- f(x).                       
 a(1).     
 b(1).     
 c(1).
 b(2).     
 c(2).     
 d(2).
 f(3).

 ?- p(x). 
    2.  p(1). 
 p(2) :- !.
 p(3).

 ?- p(x).       ?- p(x), p(y).    ?- p(x), !, p(y).
  14. Consider the following predicates person, female, and male. 
        person(P,female) :- woman(P).
    person(P,male) :- man(P).
    woman(anna). ...
    man(peter). ...
    a) Please give the Answer tree for the query person(P,K).

    b) Please optimize predicate person using !.

    c) Is your cut in part b) green or red?

  15. Suppose the following definiton of predicate memberc(X,L) is given. 
    memberc(X,[X|_]) :- !.
memberc(X,[_|L]) :- memberc(X,L).
    Please compare this definition with the ordinary one of member(X,L).

  16. Suppose the following definiton of a predicate maximum is given.
     maximum(X,Y,X) :- X >= Y, !.
 maximum(X,Y,Y).
    Then Prolog answers "incorrectly" to the question
     ?- maximum(5,2,2).
 yes
    Why does Prolog answer "yes" and how this error can be fixed (nor eliminating the cut or modifying the the fact)?