% ====================================================
:- pred constr(bool). 
:- mode constr(in). 
:- ignore constr/1.

% ====================================================
% Program. mergesorting in ascending order.E.g., 3 =< 5 =< 5 =< 8 =< ...
:- pred mergesort(list(int),list(int)).
:- mode mergesort(in,out).
mergesort([], []).
mergesort([H], []). % error: [] ---> [H]
mergesort([H,K|T],S) :-
   cons(K,T,KT),          
   cons(H,KT,HKT),          
   split(HKT,L1,L2),       
   mergesort(L1,S1),       
   mergesort(L2,S2),
   merge(S1,S2,S).         % merging

:- pred cons(int,list(int),list(int)).
:- mode cons(in,in,out).
cons(H,T,[H|T]).

:- pred split(list(int),list(int),list(int)).
:- mode split(in,out,out).
split(L,L1,L2) :- N1=(N div 2),    
     length(L,N),                    
     takedrop(N1,L,L1,L2).

:- pred length(list(int),int).
:- mode length(in,out).
length([],L) :- constr(L=0).
length([H|T],L) :-
  L=(LT+1),
  length(T,LT).

:- pred takedrop(int,list(int),list(int),list(int)).
:- mode takedrop(in,in,out,out).
takedrop(N,[],[],[]).
takedrop(N,L,[],L) :- N=<0.
takedrop(N,[H|T],[H|T1],L) :- 
  N>=1, N1=(N-1),  
  takedrop(N1,T,T1,L).

:- pred merge(list(int),list(int),list(int)).
:- mode merge(in,in,out).
merge([],L,L).                 
merge([X|Xs],[],[X|Xs]).
merge([X|Xs],[Y|Ys],[X|Zs]) :-
     X=<Y, cons(Y,Ys,YYs),
     merge(Xs,YYs,Zs).
merge([X|Xs],[Y|Ys],[Y|Zs]) :-
     X>Y, cons(X,Xs,XXs),
     merge(XXs,Ys,Zs).
     
% ====================================================
% catamorphism 
:- pred listmember(int,list(int),bool).
:- mode listmember(in,in,out).
:- cata listmember/3-2.

listmember(X,[],Res) :- constr(~Res).
listmember(X,[Y|Ys],B) :-
      constr( B=ite(X=Y,true,B1) ) ,
      listmember(X,Ys,B1).

  
% ====================================================
% verification. 
% Property:
:- pred ff1.
ff1 :-                               % mergesort
   constr(~(SL=SS)), 
   listmember(X,L,SL), listmember(X,S,SS),  
   mergesort(L,S).

% contracts (postcondition: true)

:- spec merge(A,C,E) ==> listmember(X,A,B), listmember(X,C,D), listmember(X,E,F).

:- spec split(E,A,C) ==> listmember(X,E,SE), listmember(X,A,SA), listmember(X,C,SC).

:- spec cons(C,A,D) ==> listmember(X,A,SA), listmember(X,D,SD).

:- spec takedrop(G,A,E,C) ==> listmember(X,A,B), listmember(X,E,F), listmember(X,C,D).

% ================================================================= 
:- query ff1/0.
% =================================================================