%  Version 1.1 2020-10-02

%The following programs correspond to exercise 1.

% longer(LL, L) - list LL is longer than list L, provided that LL is a list

%Base case: a list with at least one element is longer than the empty list.
%What would happen if we used the base case longer([_], []) instead?
longer([_|_], []).
%Recursive case: if Xs is longer than Ys then [_X|Xs] is longer than [_Y|Ys].
longer([_X|Xs], [_Y|Ys]) :- longer(Xs, Ys).

% evenlength( L ) - L is a list of even length

%Base case: the empty list has length 0, which is even.
evenlength([]).
%Recursive case: if Xs has even length then adding two elements to Xs
%still results in a list of even length.
evenlength([_X,_Y|Xs]) :- evenlength(Xs).

% last( Last, L ) - Last is the last element of list L

%last/2, standard recursive solution.
%Base case: the last element in a list with only one element X, is simply X.
last([X], X).
%Recursive case: if Y is the last element in Xs, then it is also the
%last element in any list obtained by adding one element in the front.
last([_X|Xs], Y) :- last(Xs, Y).

%But can also be solved with append/3.
last1(Xs, X) :- append(_, [X], Xs).


% nrev( L1, L2 ) -  L2 is the list L1 reversed

%Naive reverse using append/3. What is the (worst-case) complexity?
%the call to append is linear w.r.t. length of second list, and we
%will have a linear number of calls = O(n^2) time.

nrev([], []).
nrev([X|Xs], Ys) :- nrev(Xs, Ys1), append(Ys1, [X], Ys).

%However, the problem is solvable in linear time
% Operationally, the additional argument works as a stack

rev(Xs, Ys) :- rev(Xs, [], Ys).

% rev(List, T, L) -  List=[e1,...,en],  L=[en,...e1|T]   (n>=0).

rev([], Ys, Ys).
rev([X|Xs], Ys, Zs) :- rev(Xs, [X|Ys], Zs).

%The following programs correspond to exercise 2.

%We choose to represent a byte as list with 8 bits. Other representations are possible but using a list is the easiest choice. We define an auxillary predicate bits/1 which goes through the elements and check that they are indeed bits.
byte([B1,B2,B3,B4,B5,B6,B7,B8]) :- bits([B1,B2,B3,B4,B5,B6,B7,B8]).

bits([]).
%If Bs contains only bits then [0|Bs] only contains bits.
bits([0|Bs]) :- bits(Bs).
%If Bs contains only bits then [1|Bs] only contains bits.
bits([1|Bs]) :- bits(Bs).

%All of the following three exercises can be solved in a very simple way: no recursive problem solving is necessary.

right_shift([B1,B2,B3,B4,B5,B6,B7,B8], [0,B1,B2,B3,B4,B5,B6,B7]).

left_shift([B1,B2,B3,B4,B5,B6,B7,B8], [B1,B2,B3,B4,B5,B6,B7,0]).

circular_shift([B1,B2,B3,B4,B5,B6,B7,B8], [B8,B1,B2,B3,B4,B5,B6,B7]).


%The following programs correspond to exercise 3.

% nonmember0(E, List) - List is a list, and E is not its member
% (The name is chosen to avoid name clashes with any built-in predicates.)

nonmember0(_, []).
nonmember0(X, [Y|Ys]) :- 
    dif(X,Y),
    nonmember0(X, Ys).

%With the help of this predicate, uniquify is then rather
%straightforward. We use the built-in predicate member/2 to check
%whether an element occurs in a list. We have two recursive cases
%depending on whether the current element contains a duplicate element
%or not.

% uniquify( List1, List2 ) - List1,List2 are lists;  List2 contains the same
%                            elements as List1, but without repetition

uniquify([], []).
uniquify([X|Xs], [X|Ys]) :- 
    nonmember0(X, Xs),
    uniquify(Xs, Ys).
uniquify([X|Xs], Ys) :- 
    member(X, Xs),
    uniquify(Xs, Ys).

%The problem can also be solved by using the built-in predicate
%sort/2, which removes duplicate elements. However, this would in
%general not be an acceptable answer at an exam.
uniquify_simple(Xs, Ys) :- sort(Xs, Ys).

