Comment crée en Prolog une fonction de trie par fusion ?

trieInsersion.pl

%% % % % % % % % % % % % % % % % % % % % % % % % %
%% Topic  : Implementation d'un trie par insersion en Prolog
%% % % % % % % % % % % % % % % % % % % % % % % % %

%% % % % % % % % % % % % % % % % % % % % % % % % %
%% Spécification -> tri
%%
%%        |     ^
%%        v     |
%% tri(Liste,Trier) est vrais si est seulement si `Trier` contient tous les 
%% nombres de `Liste` ordonée par ordre croissent
%% 
%% Ex : 
%%  ?-tri([8,5,1,7,2,3],[1,2,3,5,7,8])
%%    vrai
%%
%%  ?-tri([8,5,1,2],[1,2,8,5])
%%    faux 
%%
%% % % % % % % % % % % %
%% Réalisation -> tri
%% Analyse de `Liste`
%% 
%% a) Liste=[]
%%    A quelle condition a-t-on tri([],Trier) ?
%%    A la condition que `Trier` = [].
%%    ==> tri([],[]). % Déclaration N°1
%%
%% b) List!=[]
%%    A quelle condition a-t-on tri(List,Trier) ?
%%    A la condition que l'on insert par ordre croissant chaque element de List dans un nouvelle accumulateur vide.
%%    ==> tri(List,Trier):-triAcc(List,[],Trier).
%%
%% Voir spécification triAcc si dessous.
%% % % % % % % % % % % % % % % % % % % % % % % % % %

%% % % % % % % % % % % % % % % % % % % % % % % % % %
%% Spécification -> triAcc
%%
%%         |   | ^   ^
%%         v   v |   |
%% triAcc(List,Acc,Trier) est vrais si est seulement si `Trier` contient tous les 
%% nombres de `Liste` ordonée par ordre croissent. Et Acc est une liste vide []
%% 
%% 
%% Ex : 
%%  ?-triAcc([8,5,1,7,2,3],[],[1,2,3,5,7,8])
%%    vrai
%%
%%  ?-triAcc([8,5,1,7,2,3],[],[1,5,7,8,2,3])
%%    faux
%%
%%  ?-triAcc([8,5,1,2],[5,8],[1,2,5,8])
%%    faux 
%% 
%% % % % % % % % % % % %
%% Réalisation -> triAcc
%% Analyse de `List`
%% 
%% a) List=[]
%%    A quelle condition a-t-on triAcc([],Acc, Trier) ?
%%
%%    A la condition que `Trier` = `Acc`. Car ce cas ne nous interesse pas.
%%    En effet one ne souhaite ici pas retrouve la liste inisiale à parir de la trier
%%    on bloque donc cette possibilité par se moyen
%%    ==> triAcc([],TrierAcc,TrierAcc).
%% 
%% b) List!=[]
%% b) List != []. List=[Pr|Fin]
%%    A quelle condition a-t-on triAcc([Pr|Fin],Acc,Trier) ?
%%    
%%    A la condition que l'on réalise une insertionOrdonner de Pr dans l'accumulateur
%%    Puis que l'on appel à nouveau la fonction triAcc avec le nouvelle acumulateur 
%%    (contenant la list trier par l'insersion) et la Fin de la list 
%%    ==>triAcc([Pr|Fin],Acc,Trier):-insertionOrdonner(Acc,Pr,NAcc),triAcc(Fin,NAcc,Trier).
%%
%% Voir spécification insertionOrdonner si dessous.
%% % % % % % % % % % % % % % % % % % % % % % % % % %

%% % % % % % % % % % % % % % % % % % % % % % % % % %
%% Spécification -> insertionOrdonner
%% 
%%                     |        |          ^
%%                     v        v          |
%% insertionOrdonner(ListIn,AppendValue,ListOut) est vrais si est seulement si
%% `ListOut` contient `ListIn` ainci que `AppendValue` placer avant une valeur
%%  plus grand que lui et aprés une valeur plus petite ou egal à lui
%% 
%% Ex : 
%%  ?-insertionOrdonner([8,5,1],4,[4,8,5,1])
%%    vrai
%%
%%  ?-insertionOrdonner([5,8,3],6,[5,6,8,3])
%%    vrai
%%
%%  ?-insertionOrdonner([8,2,3],8,[8,2,8])
%%    faux
%%
%%  ?-insertionOrdonner([5,1,2],8,[5,8,1,2])
%%    faux  
%% 
%% % % % % % % % % % % %
%% Réalisation -> insertionOrdonner
%% Analyse de `ListIn`
%% 
%% a) List=[]
%%    A quelle condition a-t-on insertionOrdonner([],AppendValue,ListOut) ?
%%
%%    A la condition que ListOut = [AppendValue]
%%    ==> insertionOrdonner([],AppendValue,[AppendValue]).
%% 
%% b) List!=[]
%% b) List=[Pr|Fin]
%%    A quelle condition a-t-on insertionOrdonner([Pr|Fin],AppendValue,ListOut) ?
%%
%%    A la condition que AppendValue soit placer dans ListOut si AppendValue =< Pr
%%    De cette façon la valeur précédente et bien inférieur à notre valeur à ajouter
%%    Cette déclaration mettra alors fin à la récurrsion
%%    ==>insertionOrdonner([Pr|Fin],AppendValue,[AppendValue,Pr|Fin]):-lte(AppendValue,Pr). % lte correspond juste au test AppendValue=<Pr
%% 
%% Analyse de `ListOut` et `ListIn`
%%  
%% a) ListOut!=[] && List!=[]
%% a) ListOut=[Pr|NFin] && List=[Pr|Fin]
%%    A quelle condition a-t-on insertionOrdonner([Pr|Fin],AppendValue,[Pr|NFin]) ?
%%  
%%    A la condition que AppendValue>Pr on alors on récupére une nouvelle itération de la récursion en se rappelant une fois
%%    ==>insertionOrdonner([Pr|Fin],AppendValue,[Pr|NFin]):-gt(AppendValue,Pr),insertionOrdonner(Fin,AppendValue,NFin). % gt correspond juste au test  AppendValue>Pr
%% % % % % % % % % % % % % % % % % % % % % % % % % %


% Juste pour encapsuler X > Y  
gt(X,Y):-
    {X>Y}.

% Juste pour encapsuler X =< Y
lte(X,Y):-
    {X=<Y}.  
  
% Tri
tri([],[]).
tri(List,Trier):-triAcc(List,[],Trier).

% TriAcc
triAcc([],TrierAcc,TrierAcc).
triAcc([Pr|Fin],Acc,Trier):-insertionOrdonner(Acc,Pr,NAcc),triAcc(Fin,NAcc,Trier).

% Insersion
insertionOrdonner([],AppendValue,[AppendValue]).
insertionOrdonner([Pr|Fin],AppendValue,[AppendValue,Pr|Fin]):-lte(AppendValue,Pr).
insertionOrdonner([Pr|Fin],AppendValue,[Pr|NFin]):-gt(AppendValue,Pr),insertionOrdonner(Fin,AppendValue,NFin).