Exercises (Prolog)

1. A predicate 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 oraz fac/2, fib/2 i gcd/3 analogous.
   
   
2. Suppose predicates parent/2, female/1 i male/1 wth 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 supposed to be represented by ordinary lists, for example [x,l,v,i,i] denotes 47.
   
   
5. Please define predicates plus/3, times/3, fib/2 oraz sum-up/2 (using recursion).
   Predicate sum-up(N,X) is fulfilled, if X is the sum from 0 to N.
   
   
6. Predicate sil/2 can also be defined as follows:

     sil(X,N) :- sil(X,N,1).
   
     sil(0,A,A).
     sil(X,N,A) :- X > 0, A1 is A * X, X1 is X - 1, sil(X1,N,A1).
   

   Please define the predicatess from exercise 5 using this technique. (Note: The variable A of sil/3 is called accumulator.)
   
   
7. 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: ?-q_i(tom,pat). and ?-q_i(liz,jim) for i = 1, ... 4.
   
   
8. 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] 

9. 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]).
   

10. 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.
       
       
11. 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.)
    
    
12. 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 largest 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.
    
    
13. 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). 

14. Please give the answer trees for the following queries
    

    1.  append1([],L,L).
        append1([H|L1],L2,[H|L3]) :- append1(L1,L2,L3).
       
        append2([H|L1],L2,[H|L3]) :- append2(L1,L2,L3).
        append2([],L,L).                                   ?- appendi(X,[3,4],[2,3,4]).
       

    2.  is_list([]).
        is_list([X|L]) :- is_list(L).                      ?- is_list(L).
       

15. 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). 

16. 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).
    
    
17. 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)?
    
    
18. Suppose given are a list of properties, for example [animate, male, canine, feline], and a list of clauses such as

     animate(fred).
     animate(alice).
     male(fred).
     canine(alice).
     feline(fred).
    

    Please define a predicate checkprops(P,L), where P is a person and L a list of properties. checkprops(A,L) is fulfilled, if P has all properties from L.
    Examples:

     ?- checkprops(fred, [animate, male]).
     yes
     ?- checkprops(alice, [animate, feline]).
     no
    

19. Please define a predicate filter(P,L1,L2), which is fulfilled if list L2 contains all elements from list L1 fulfilling predicate P.
    Example:

     pos(X) :- X > 0.
     neg(X) :- X < 0.
    
     ?- filter(pos,[1,2,0,5,-5,-6,8],L).
     L = [1,2,5,8]
     ?- filter(neg,[1,2,0,5,-5,-6,8],L).
     L = [-5,-6]