% 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).