% ------------------------------------------------------------------
% 5.1: reverse
% ------------------------------------------------------------------

% naive_reverse

naive_reverse(list)  **> list.
naive_reverse([])    :=  [].
naive_reverse([H|T]) :=  append(naive_reverse(T),[H]).


% basic append required for naive_reverse

append(list,list) **> list.
append([],List) := List.
append([H|T],L) := [H|append(T,L)].



% Prolog version of reverse
%
% reverse(A,B) :- reverse_aux(A,[],B).
% reverse_aux([],L,L).
% reverse_aux([H|T],L,Result) :- reverse_aux(T,[H|L],Result).


reverse(list) **> list.
reverse(L)    :=  reverse_aux(L,[]).

reverse_aux(list,  list) **> list.
reverse_aux([],    L)    :=  L.
reverse_aux([H|T], L)    :=  reverse_aux(T,[H|L]).

delay(reverse_aux, (arg1:tl*e_list ; arg0: tl*e_list)).


% ------------------------------------------------------------------
% 5.2: permute
% ------------------------------------------------------------------

insert(list,string) **> list.
insert(L,X) := [X|L].
insert([H|T],X) := [H|insert(T,X)].

permute(list) **> list.
permute([]) := [].
permute([H|T]) := insert(permute(T),H).


% ------------------------------------------------------------------
% 5.3: select
% ------------------------------------------------------------------
% select an element which occurs in a specified list, return the rest

select(list,bot) **> list.
select([X|R],X)  :=  R.
select([F|R],X)  :=  [F|select(R,X)].
 

% ------------------------------------------------------------------
% extra
% ------------------------------------------------------------------

% append with reversed clause order
append1(list,list) **> list.
append1([H|T],L) := [H|append1(T,L)].
append1([],List) := List.

delay(append1, ( arg0: @list 
               ; arg1: @list)).



% special_append: an append optimized for delaying
special_append(list,          list)         **> list.
special_append([],            [])           :=  [].
special_append([],            (L,ne_list))  :=  L.
special_append((L,ne_list)   ,[])           :=  L.
special_append([(H,string)|T],(L,ne_list))  :=  [H|special_append(T,L)].

delay(special_append, ( arg0: e_list
                      ; arg1: e_list 
                      ; arg2: e_list
                      ; arg0: @list
                      ; arg1: @list)).