PROG 1 4th Quarter April 22, 2005        Name ______________________
Attach code and sample runs (more than one run for each)
Prolog exercises 1

1. Consider

he function f defined as:
	f(x) = x - 10 if x > 100,
	f(x) = f(f(x+11)) if x <= 100.

  A. Write a Prolog procedure f(X,Y) that defines Y as the value of 
   the function f for any integer X.

  B. What are the outputs for X = 95, 5, 9?

2. Let L and L1 denote two lists of terms.  Write Prolog procedures to:

  A. Delete all occurences of element X in L, giving the results in L1.

  B. Replace all occurences of element X in L with element Y, giving the 
    results in L1.

Here's the code to delete the first occurrence of an element in a list:
MAKE SURE YOU UNDERSTAND HOW THIS IS WORKING

del(_,[], []).
del(X,[X|Rest],Rest).
del(X,[Y|Rest],[Y|NewList]) :- /* This line..[Y|NewList]..acts like an append*/
	del(X,Rest,NewList).


|?- del(a,[c,d,b,s,a,s,a,a,a,a,e],X).

X = [c,d,b,s,s,a,a,a,a,e] ? 

yes
| ?- del(z,[c,d,b,s,a,a,s,a,a,a,a,e],X).

X = [c,d,b,s,a,a,s,a,a,a,a,e] ? 



3. Let L be a list of terms. Write Prolog programs for each of the following definitions:
  A. dellast2(L, L1).  Defines L1 to be obtained from L with the last 2 elements removed.
 
  B. trim(N,L,L1).  defines L1 to be obtained from L with the first N elements removed.

Here's the code to delete the last element of a list:

dellast([_|[]], []).
dellast([X|Rest],[X|NewList]) :-
   	dellast(Rest,NewList).

|?- dellast([a,s,d,c,f],X).

X = [a,s,d,c] 



4. Run the following Prolog program.  Explain what it is doing.

  mystery([],1).
  mystery(X,0) :- X \= [], atomic(X).
  mystery([X|Y], N) :- mystery(X,Q), mystery(Y,P),
  		       Q1 is Q + 1, max(P,Q1,N).

  max(A,B,A) :- A >= B.
  max(A,B,B) :- A < B.

5. Count and Sum the elements in a list (you've seen these before, now try in Prolog!)
 A. Count the elements in a "flat" list.
   ?- count([a,c,[4,[v,h]]], Number).  
    Number = 3

 B. Count the elements in a non-flat, embedded list structure.
   ?- countall([a,c,[4,[v,h]]], Number).
    Number = 5

 C. Sum the elements in a "flat" list.
   ?- sum([10,12,4, 3,7], Number).  
    Number = 36

 D. Sum the elements in a non-flat, embedded list structure.
   ?- sumall([10,12,[4,[3,7]]], Number).
    Number = 36

 
6. Interleave the elements from 2 lists.
  ?-merge([a,b,c,d],[1,2,3,4], X).
    X = [a,1,b,2,c,3,d,4].

  Also try a version that will work for lists of different lengths.

7. Find the maximum value in a list.
  ?- max([34,1,6,50,2,8], Max).
   Max = 50