Lab 4

1. Discuss the solution to Assignment 1
-----------------------------

2. List Manipulation
-------------------------

Write each of the following predicates with the students. 

a. A predicate to compute the third element of a list 
(fails if the list has less elements).

?- third([a,b,c,d],X).
X = c 
yes

?- third([a,b],X).
No

Solution:
  third([_,_,X|_],X).



b. Delete first occurrence of one element from the list (surface level only):

del1(_,[],[]).  %needed only if tests like del1(4,[],L).
del1(X, [X | Tail], Tail).
del1(X, [Y | Tail], [Y | Tail_1]) :-
        X\=Y, del1(X, Tail, Tail_1).


Delete all occurrences of one element from a list (surface level only)
del(_, [], []).
del(X, [X | Tail], Tail_1) :- del(X, Tail, Tail_1).
del(X, [Y | Tail], [Y | Tail_1]) :-  X\=Y, del(X, Tail, Tail_1).
% \= needed to avoid multiple solutions whne there shoudl be only one


c. Remove duplicate occurrences of an element

   rm-dups(L1,L2) -- L2 is the same as L1 with the
second and succeeding immediately adjacent duplicates
removed.

   For example:

?- rm-dups([a,b,a,a,a,c,c],[a,b,a,c]).
Yes
?- rm-dups([a,b,a,a,a,c,c],X).
X = [a, b, a, c] ;
No
?- rm-dups([a,b,a,a,a,c,c],[a,b,c]).
No


Solution:   Pre-req: L1 is fully instantiated, L1 and L2 are lists.
 
   rm-dups([],[]).
   rm-dups([X],[X]).
   rm-dups([X,X|Rest],Rest2) :- rm-dups([X|Rest],Rest2).
   rm-dups([X,Y|Rest],[X|Rest2]) :- X \= Y, rm-dups([Y|Rest],Rest2).

*** If we don't add X\=Y to the last clause, we get the
correct solution, but when we ask for more solutions we
get some (and we shouldn't).



d. Count element occurrences.

    count(L,E,N) holds if the list L contains E N times.
    Precondition: L and E are instantiated. L is a non-nested list.

?- count([1,2,1,1],1,3).
Yes
?- count([1,2,1,1],1,N).
N = 3 ;
No
?- count([1,2,1,1],1,2).
No
?- count([1,2,[1,2],1],[1,2],N).
N = 1 ;
No

    Solution:
    count([],_,0).
    count([E|Rest],E,N) :- count(Rest,E,N1), N is N1 + 1.
    count([X|Rest],E,N) :- X \= E, count(Rest, E, N).

*** N1 has to be instantiated when we compute N.
*** X\=E means X does not unify with E.