HW4 - Prolog II

Define the following predicates: In the tradition of Logic programming, each predicate is defined by what will make that predicate true. Further the arity of the function is indicated in the description and by the /# notation introduced in class. Assume that each predicate's signature consists of all arguments being (possibly) non-grounded.




  1. Due to the spirit of this assignment, you may not convert the list to a normal list and then process it. All functions must process difference lists.  

  2. You may assume that all difference lists given as arguments to the difference list predicates are valid difference lists, as defined in class.  

  3. Predicates that you define for other problems may be used in the solution of any particular problem.  

  4. All predicates must be written by you. Further the ideas must be your own.  






  1. mem_dl -- mem_dl is true when it's first argument is a member of the second argument. The second argument is constrained to be a difference list.  This predicate should have an open signature, i.e. it will accept 0 of its arguments as being grounded. This predicate may produce redundant solutions.
    ?- mem_dl(t, [a, b, c, d, t, g, h]-[d, t, g, h]).
    
    No.
    
    ?- mem_dl(a, [a, b, c, d, t, g, h]-[d, t, g, h]).
    
    Yes.
    
    ?- mem_dl(X, [a,b,c]-[]).
    
    X = a ;
    
    X = b ;
    
    X = c ;
    
    No.
    
    ?- mem_dl(a, X).
    
    X = [a|_G1]-_G1 ;
    
    X = [_G1,a|_G2]-_G2 .
    
    Yes.
    
  2. empty_dl -- empty_dl is true when the argument given to it is a difference list, which is empty.  This should accept the signatures: empty_dl(+), or empty_dl(-).
    ?- empty_dl([]-[]).
    
    Yes.
    
    ?- empty_dl([a,b,c]-[a,b,c]).
    
    Yes.
    
    ?- empty_dl([a,b,c]-[b,c]).
    
    No.
    
  3. equal -- equal is true when the two lists given to it as arguments are equivalent, this predicate should work on either difference lists or normal lists.  This predicate should accept the signatures: equal(+,-), equal(-,+), equal(+,+).
    ?- equal([]-[],[]-[]).
    
    Yes.
    
    ?- equal([a,b]-[b],[a,b]-[]).
    
    No.
    
    ?- equal([c, d]-[d],[c,d]-[d]).
    
    Yes.
    
    ?- equal([],[]-[]).
    
    Yes.
    
    ?- equal([a], [a,b,c,d,e,f]-[b,c,d,e,f]).
    
    Yes.
    
    ?- equal([a], [a,b,c,d,e,f]-[c,d,e,f]).
    
    No.
    
  4. length_dl -- length_dl is true when the second argument, which should be a number, is equal to the number of elements in the difference list that is the first argument.  This should accept any of the signatures: length_dl(+,-), length_dl(-,+), or length_dl(+,+).
    ?- length_dl([a,b,c,d,e,f]-[e,f], X).
    
    X = 4 ;
    
    No.
    
    ?- length_dl([a,b]-[],X).
    
    X = 2 ;
    
    No.
    
    ?- length_dl([]-[], X).
    
    X = 0 .
    
    Yes.
    
    ?- length_dl(X, 3).
    
    X = [_G1,_G2,_G3|G4]-G4 .
    
    Yes.
    
  5. samelen_dl -- samelen_dl is true when the two difference lists given to it are of the same length. This predicate should accept the signature samelen_dl(+,+).
    ?- samelen_dl([a,b,c,d,e,f]-[d,e,f], [g,h,i,j,k,l,m]-[j,k,l,m]).
    
    Yes.
    
    ?- samelen_dl([a,b,c,d,e,f]-[e,f], [g,h,i,j,k]-[k]).
    
    Yes.
    
    ?- samelen_dl([a,b,c,d,e,f]-[e,f], [a,b,c,d,e,f]-[e,f]).
    
    Yes.
    
    ?- samelen_dl([a,b,c,d,e,f]-[e,f], [a,b,c,d,e,f]-[c,d,e,f]).
    
    No.
    
    
  6. samelen -- samelen is true when the two lists given to it as arguments have the same length. It should be able to take either difference lists or normal lists.   This predicate need only accept the signature samelen(+,+).
    ?- samelen([a,b,c,d,e,f]-[d,e,f],[a,b,c,d,e,f,g]-[d,e,f,g]).
    
    Yes.
    
    ?- samelen([a,b,c,d,e,f]-[d,e,f],[t,y,z]).
    
    Yes.
    
    ?- samelen([a,b,c,d,e,f]-[d,e,f], [a,b,c,d,e,f]-[c,d,e,f]).
    
    No.
    
    ?- samelen([a,b,c,d,e,f],[w,x,y,z,q,r]).
    
    Yes.
    
    ?- samelen([a,b,c,d,e,f], [w,x,y,z]).
    
    No.
    
    ?- samelen([a,b,c,d],[a,b,c,d]-[d]).
    
    No.
    
    ?- samelen([], [a,b,c|X]-[a,b,c|X]).
    
    Yes.
    
    
Your file should contain ALL functions necessary for the assignment, do not run the script several times to hand in different portions of the assignments.  Please be sure your file loads and runs properly on swiprolog as installed on the CS machines. Turn it in by running eg
~bap/bin/handin hw4.pl
on a regular UNM CS machine.

Due: 3:30pm, Wed Oct 10.


Barak Pearlmutter <bap@cs.unm.edu>
Shawn Stoffer <storm@cs.unm.edu>