HOMEWORK 4, Part 1.

Deadline: Friday, December 9.

1. Given a list of elements colored red, white, and blue, reorder 
the list so that all the red elements appear first, then all the
white elements, followed by the blue elements. The reordering should
prserve the original relative order of elements of the same color.
Sample run:

?- reorder([red(1), white(2), blue(3), red(4), white(5)], Reordered].

Reordered = [red(1), red(4), white(2), white(5), blue(3)];

no

Write two versions of the reordering program: with and without difference
lists.

============

2. Implement two versions of the quicksort algorithm: with and without 
difference lists.

============

3. Write the following as a set of Prolog predicates:

Eat at the restaurant if it looks nice but if it stinks don't eat there

using:
(a) cut and fail combination
(b) the 'not' predicate.

============

4.  Consider the following program which is supposed to insert its first argument, 
a number, into its second argument, a sorted list, giving the third argument 
(also a sorted list):

  insert(X,[H|T],[H|T1]) :- X>H, !, insert(X,T,T1).
  insert(X,L,[X|L]).

   1. Provide an appropriate query to show that this program is incorrect
   2. Change the program so that it works correctly 

============

5. Write a ternary predicate delete_all(item,list,result) that is true if result is
obtained from list by deleting all occurrences of item. Use cut to prevent backtracking.
Sample run:

?-delete_all(a,[a,b,c,a,d,a],X).

X=[b,c,d];

No


?-delete_all(a,[b,c,d],X).

X=[b,c,d];

No

=============

6. Write a binary predicate count_occurrences(input,result) that is true if 'result' is
a list of two-element lists [el, number_of_occurrences_in_input], where 'el' is an element of
the list 'input', and 'number_of_occurrences_in_input' is an integer specifying how many times
'el' occurs in 'input'. For each element 'el' in 'input' there should be a corresponding pair
[el, number_of_occurrences_in_input] in 'result'.
Sample run:

?- count_occurrences([a,b,a,a,b,c],X).

X = [[c, 1], [b, 2], [a, 3]] ;

No

=============

7. Write a ternary predicate delete_nth that deletes every N'th element from a list. Sample runs:

7 ?- delete_nth([a,b,c,d,e,f],2,L).

L = [a, c, e] ;

No
8 ?- delete_nth([a,b,c,d,e,f],1,L).

L = [] ;

No
9 ?- delete_nth([a,b,c,d,e,f],0,L).

No
10 ?- delete_nth([a,b,c,d,e,f],10,L).

L = [a, b, c, d, e, f] ;

No


==============

8. Sketch the steps of the unification algorithm on the pairs below:

a) f(a,x,g(y)) and f(z,y,x)
b) f(x,y,z,w) and f(f(u,u),f(x,x),f(y,y),f(z,z))

f and g are function symbols, x,y,z,u,w are variables, a,b,c,d are constants.