%****************************************************************
%                 A Little LIST PROCESSING
% 
%  Lists are an important and fundamental data structure in
%         any practical LP language like PROLOG.
%****************************************************************

:- ensure_loaded('utilities').


%==========================================================
% First element of a list
%==========================================================

first([First | Rest],First).

%==========================================================
%
% An element is a member of a list
%  if it is the first element or if it is
%  a member of the Tail of the list.
%
%==========================================================
my_member(H,[H | _]).
my_member(H,[_ | T]) :- my_member(H,T).


%==========================================================
% Another version of member. How is it
%  different.
%==========================================================
isMember(H,[H | _]) :- !.
isMember(H,[_ | T]) :- isMember(H,T).


%==========================================================
% insert
%
%  -True for List,X,NewList where NewList
%     is List with X inserted in any position.
%  -There are as many solutions are there are positions
%    in List. 
%
%  -Terminates because not(=([],[H | T]]).
%
%  -Trying calling with only the last argument bound
%  -Tring calling with first two arg. bound.
%==========================================================

%
%True of X is in the first position
%
insert(L,X,[X | L]).

%
%True of X is in the first position of any "tail" of Input List
%
insert([H | T],X,[H | L]) :- 
    insert(T,X,L).

%==========================================================
% Generate Permutations of a List
%
%   - A Permutation of a list is a permutation
%     of the tail with the first inserted in the tail
%     at every possible position.
%
% Recursively traverses the list til the end
% as it builds the list back up it permutes each added
% element using insert.
%
% Example Trace building list back up: calls to insert
%   		[],c--->[c]
%
%              	[c],b-->[b,c],[c,b]
%
%		[b,c],a-->[a,b,c],[b,a,c],[b,c,a]
%		[c,b],a-->[c,b,a],[c,a,b],[c,b,a]
%
% Dummy gets "counted down" to ensure
%   termination in case first arg is a variable.
%
%
%==========================================================
perm(Xs,Ys) :-
    perm(Xs,Ys,Ys).

perm([],[],[]).
perm([X | Xs],Y1s,[_ | Dummy]) :-  	
       perm(Xs,Ys,Dummy), %
       insert(Ys,X,Y1s).  %


%==========================================================
% Are two lists permutations of one another
%==========================================================
isPerm([],[]).
isPerm([X | Xs],Ys) :-
         isMember(X,Ys),
         del(X,Ys,Y1s),
         isPerm(Xs,Y1s).

%==========================================================
% Delete an element from a list.
%==========================================================
del(X,[],_) :- fail,!.
del(X,[X | Ys],Ys) :- !.
del(X,[H | Ys],[H | Y1s]) :-
        del(X,Ys,Y1s).
          

%==========================================================
% The Length of a list is one plus the length
%    of its tail.
%==========================================================
list_len([],0).
list_len([_|Tail],N) :-
     list_len(Tail,M),
     N is M + 1.

%==========================================================
% Appending Two Lists.
%==========================================================
%Base Case
%
%A list L is the empty list appended to L
%
appnd([],L,L).

%Inductive Step
%
% A new list with the Head H and the tail TL is
% the result of appending a list with the head H and the tail T
% to a list L where TL is the result of appending the tail of the first list T to L.
%
appnd([H | T],L,[H | TL]) :-
           appnd(T,L,TL).


%==========================================================
% Reversing a List with simplicity.
%
% The Reverse of a list can be
%  described as the First attached to the end of 
%  the reverse of the Rest
%==========================================================
my_reverse([],[]).
my_reverse([First | Rest],Rev) :-
	my_reverse(Rest,RevRest),
	append(RevRest,[First],Rev).

%==========================================================
% Reversing a List with Expertise
%
%   A PROLOG naturally traverses the list "PUSH" the
%    the elements on another list.
%==========================================================
better_reverse(L,ReversedL) :-
	better_reverse(L,[],ReversedL).

better_reverse([],Reversed,Reversed).
better_reverse([X | Xs],Stack,Reversed) :- 
	better_reverse(Xs,[X | Stack],Reversed).


%==========================================================
% Build a list of a given size
%==========================================================
build_list(Size,Element,List) :-
	build_list(Size,Element,[],List).

build_list(0,_,List,List) :- !.
build_list(Size,Element,Stack,List) :-
	Size > 0,
	S is Size - 1,
	build_list(S,Element,[Element | Stack],List).

	
/*
Try These queries and compare results
	build_list(200,x,L),ms(my_reverse(L,R),Time).

	build_list(200,x,L),ms(better_reverse(L,R),Time).
*/