ASSIGNMENT 3. Due January 18.

Please submit the solutions in ONE Prolog file, where everything except the 
source code is put in the comments.

================================================================================
1.
   - Compute E\theta, where E=f(x,f(x,b,y),g(a,z)) and \theta= {x -> y, y -> g(a,z), z -> x\}.

   - Compute \theta\sigma, where \theta={x -> f(x), y -> z, z -> g(a,y,h(x))} and
     \sigma= {x -> y, z -> y,  y -> h(y), w -> a}.

   - Compute \theta\theta, where \theta={x -> f(x), y -> z, z -> g(a,y,h(x))}.

   - Sketch the steps of the unification algorithm discussed in the class
     on the pairs of terms 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))

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

2. 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 a nonngative 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 (the order in the output list is irrelevant):

   ?- count_occurrences([], Occ).
   Occ = [].

   ?- count_occurrences([a], Occ).
   Occ = [[a, 1]].

   ?- count_occurrences([a,b,a], Occ).
   Occ = [[b, 1], [a, 2]].

   ?- count_occurrences([a,b,c,c,a,a,d], Occ).
   Occ = [[d, 1], [c, 2], [b, 1], [a, 3]].

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

3. Implement a ternary predicate flatten_term(Function_symbol, Term, Flattened_term)
   that succeeds if Flattened_term is obtained from Term by flattening out all
   nested occurrences of Function_symbol. It is assumed that Term contains no 
   Prolog variables and no lists (you don't have to check this).

   Sample runs:

   ?- flatten_term(f, f(f(x)), Flattened_term).
   Flattened_term = f(x).

   ?- flatten_term(f, f(x), Flattened_term).
   Flattened_term = f(x).

   ?- flatten_term(f, a, Flattened_term).
   Flattened_term = a.

   ?- flatten_term(f, g(f(x)), Flattened_term).
   Flattened_term = g(f(x)).

   ?- flatten_term(f, g(f(f(x))), Flattened_term).
   Flattened_term = g(f(x)).

   ?- flatten_term(f, f(g(f(x))), Flattened_term).
   Flattened_term = f(g(f(x))).

   ?- flatten_term(f, f(f(f,g(f(y)))), Flattened_term).
   Flattened_term = f(g(f(y))).
   
================================================================================

4. Implement the quicksort algorithm to sort lists. The algorithm should be
   parametrized by the ordering which compares list elements:
   quicksort(List_in, Ordering, Sorted) succeeds if 'Sorted' is the sorted
   version of 'List_in' wrt the ordering relation 'Ordering'.

   Important requirement: Do not use append. Use difference lists.

   Sample runs:
   ?- quicksort([5,4,3,4,5,6], '=<', L).
   L = [3, 4, 4, 5, 5, 6].

   ?- quicksort([5,4,3,4,5,6], '>', L).
   L = [6, 5, 5, 4, 4, 3].

   ?- quicksort([a,b,X,Y,f(a),[X|Y]], '@>', L).
   L = [[X|Y], f(a), b, a, Y, X].

   ?- quicksort([a,b,X,Y,3,f(a),[X|Y],2.5], '@<', L).
   L = [X, Y, 2.5, 3, a, b, f(a), [X|Y]].
   
================================================================================

5. Implement the predicate multiset_less(List1, List2), which succeeds, if 
   List1 is smaller than List2 with respect to the multiset extension of the 
   standard order of terms @<.

   Multiset extension of an ordering < is the ordering <_m defined as follows: 
   Let M1 and M2 be two multisets whose elements are comparable w.r.t <. Then
   M1 <_m M2 iff there exist multisets X1 and X2 such that the following three 
   conditions hold:

   - X2 is a nonempty submultiset of M2.
   - M1 = (M2 \ X2) U X1, where \ is a multiset difference and U is a multiset union.
   - For all x1 in X1 there exists x2 in X2 such that x1 < x2.

   In other words, a multiset is reduced wrt <_m by the removal of at least one
   element (those in X2) and their replacement with any finite number - possibly
   zero - of elements (those in X1), each of which is smaller wrt < than one of
   the elements that have been removed.

   For example, if < is the standard ordering on numbers, then we have
   - {3,4} <_m {3,3,4,0}
   - {3,2,2,1,1,1,4,0} <_m {3,3,4,0}
   - {3,3,3,3,2,2} <_m {3,3,4,0}

   The behavior of the program on the sample queries should be the following:

   ?- multiset_less([3,4],[3,3,4,0]).
   true.

   ?- multiset_less([3,2,2,1,1,1,4,0],[3,3,4,0]).
   true.

   ?- multiset_less([3,3,3,3,2,2],[3,3,4,0]).
   true.

   ?- multiset_less([a,b,X,Y,[X|Y],2], [[X,X|Y]]).
   true.

   ?- multiset_less([a,b,X,Y,[X|Y],2], [X,b,b]).
   false.