:- ensure_loaded(typeops_meta).

% meta-programming
%
% foldr/4 predicate
%   foldr(op, b, [e1, e2, ..., en], (e1 op (e2 op (...(en op b)...)))) 
% foldl/4 predicate
%   foldl(op, b, [e1, e2, ..., en], ((...((b op e1) op e2)...) op en))
% compose/4 predicate
%   compose(f, g, x, f(g(x)))
% converse/4 predicate
%   converse(f, x, y, f(y,x))
        
           
 
%+++++++++++++++++++++++++++++ type definitions +++++++++++++++++++++++ 

:- import_type(prolog_types).

:- suptype numexpr2 > numexpr.
:- type numexpr2 --> numexpr2 mod numexpr2.

 
%+++++++++++++++++++++++++++++ predicates  +++++++++++++++++++++++ 

:- import_pred(prolog_meta,fcall/4).
:- import_pred(prolog_meta,fcall/3).
:- import_pred(prolog_meta,fcall/2).

:- import_pred(prolog_meta,'>='/2).
:- import_pred(prolog_meta,'=<'/2).
:- import_pred(prolog_meta,'>'/2).
:- import_pred(prolog_meta,'='/2).
:- import_pred(prolog_meta,!/0).

:- pred foldr(meta((trmName(@T, @T1, @T1) of mpred)), T1, list(T), @T2)
              with T1 =< T2.
foldr(_F, B, [], B).
foldr(F, B, [A|As], R) :-
	foldr(F, B, As, R1),
	fcall(F, A, R1, R).


:- pred foldl(meta((trmName(@T1, @T, @T1) of mpred)), T1, list(T), @T2)
              with T1 =< T2.
foldl(_F, B, [], B).
foldl(F, Bs, [A|As], Cs) :-
	fcall(F, Bs, A, Bs1),
	foldl(F, Bs1, As, Cs).


% compose(f, g, x, f (g x))
:- pred compose(meta((trmName(@T2, @T3) of mpred)), 
                meta((trmName(@T1, T2) of mpred)),
	        T1, T3).
compose(F, G, X, FGX) :-
	fcall(G, X, GX),
	fcall(F, GX, FGX).


% converse(f, x, y, f y x)
:- pred converse(meta((trmName(@T1, @T2, @T3) of mpred)), T2, T1, T3).
converse(F, X, Y, FYX) :- fcall(F, Y, X, FYX).

%-----------

:- pred append(list(T), list(T), list(@T)).
append([],Xs,Xs).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).


% insert number into sorted list
:- pred insert(numexpr,list(numexpr), list(numexpr)).
insert(N,[],[N]).
insert(N, [H|L], O) :- 
	N =< H, 
	O = [N,H|L].
insert(N, [H|L0], [H|L]) :- 
	N > H, 
	insert(N, L0, L).


%-------- combined predicates

:- pred converse_append(list(T), list(T), list(@T)).
converse_append(X, Y, FYX) :- converse(append, X, Y, FYX).

:- pred foldr_append(list(list(T)), list(T)).        % append/2
foldr_append(Xs,Ys) :- foldr(append,[],Xs,Ys).

:- pred foldl_rappend(list(list(T)), list(T)).       % reverse_append/2
foldl_rappend(Xs,Ys) :- foldl(converse_append,[],Xs,Ys).


%----------------------------

:- pred converse_insert(list(numexpr), numexpr, list(numexpr)).
converse_insert(X, Y, FYX) :- converse(insert, X, Y, FYX).

:- pred isort(list(numexpr), list(numexpr)).
isort(Xs, Ys) :- foldr(insert, [], Xs, Ys).

:- pred isort_faster(list(numexpr), list(numexpr)).
isort_faster(Xs, Ys) :- foldl(converse_insert, [], Xs, Ys). % no big stack

 
%+++++++++++++++++++++++++++++ tests  ++++++++++++++++++++++++++ 

?- foldr(append, [],[[1,2,3], [5,6], [7,8,9]], X).
?- foldl(append, [],[[1,2,3], [5,6], [7,8,9]], X).
?- foldr_append([[1,2,3], [5,6], [7,8,9]], X).       % append/2

%---------

?- foldr(converse_append, [],[[1,2,3], [5,6], [7,8,9]], X).
?- foldl_rappend([[1,2,3], [5,6], [7,8,9]], X).      % reverse_append/2

%---------

?- isort([2,44,43,1,45,3,76],X).
?- isort_faster([2,44,43,1,45,3,76],X).

?- compose(isort,foldr_append,[[2,44],[43,1,45],[3,76]],X).


