Learning insertion sort.

Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.

Program source code: insertion_sort.pl

% Figure 19.10  Learning insertion sort.
 
 
% Learning sort
 
backliteral( sort( L, S), [L:list], [S:list]).
backliteral( insert_sorted( X, L1, L2), [X:item, L1:list], [L2:list]).
 
term( list, [X | L], [X:item, L:list]).
term( list, [], []).
 
prolog_predicate( insert_sorted( X, L0, L)).
prolog_predicate( X=Y).
 
start_clause( [sort(L1,L2)] / [L1:list, L2:list] ).
 
ex( sort( [], [])).
ex( sort( [a], [a])).
ex( [ sort( [c,a,b], L), L = [a,b,c] ] ).   % Uninstantiated 2nd arg. of sort!
ex( sort( [b,a,c], [a,b,c])).
ex( sort( [c,d,b,e,a], [a,b,c,d,e])).
ex( sort( [a,d,c,b], [a,b,c,d])).
 
nex( sort( [], [a])).
nex( sort( [a,b], [a])).
nex( sort( [a,c], [b,c])).
nex( sort( [b,a,d,c], [b,a,d,c])).
nex( sort( [a,c,b], [a,c,b])).
nex( sort( [], [b,c,d])).
 
insert_sorted( X, L, _) :-     % Guarding clause: test instantiation of args.
  var(X), !, fail
  ;
  var( L), !, fail
  ; 
  L = [Y|_], var(Y), !, fail.
 
insert_sorted( X, [], [X])  :-  !.
 
insert_sorted( X, [Y | L], [X,Y | L])  :-
  X @< Y, !.           % term X "lexicographically precedes" term Y 
 
insert_sorted( X, [Y | L], [Y | L1])  :-
  insert_sorted( X, L, L1).