swi Prolog - Error arguments not sufficiently Instantiated

Question

I am new to Prolog and when I query sortedUnion([1,1,1,2,3,4,4,5], [0,1,3,3,6,7], [0,1,2,3,4,5,6,7]). I get an error

Exception: (7) unite([_G114, _G162, _G201, _G231, _G243], [_G249, _G297, _G336, _G357, _G369], [0, 1, 2, 3, 4, 5, 6, 7]) ?

So I am hoping someone will be able to tell me where my code is mistaken and why it is wrong?

%undup(L, U) holds precisely when U can be obtained from L by eliminating repeating occurrences of the same element                   
undup([], []).
undup([X|Xs], [_|B]) :- remove(X,Xs,K), undup(K, B).

remove(_,[],[]).
remove(Y,[Y|T],D) :- remove(Y,T,D).
remove(Y,[S|T],[S|R]) :- not(Y = S), remove(Y,T,R).

%sortedUnion(L1,L2,U) holds when U contains exactly one instance of each element 
%of L1 and L2

sortedunion([H|T], [S|R], [F|B]) :- undup([H|T], N), undup([S|R], M), unite(N,M,[F|B]).
unite([], [], []).
unite([X], [], [X]).
unite([], [X], [X]).
unite([H|T], [S|R], [X|Xs]) :- S=H, X is S, unite(T, R, Xs).
unite([H|T], [S|R], [X|Xs]) :- H<S, X is H, unite(T, [S|R], Xs).
unite([H|T], [S|R], [X|Xs]) :- S<H, X is S, unite([H|T], R, Xs).

Answer 1

An advice first: try to keep your code as simple as possible. Your code can reduce to this (that surely works)

sortedunion(A, B, S) :-
    append(A, B, C),
    sort(C, S).

but of course it's instructive to attempt to solve by yourself. Anyway, try to avoid useless complications.

sortedunion(A, B, S) :-
 undup(A, N),
 undup(B, M),
 unite(N, M, S).

it's equivalent to your code, just simpler, because A = [H|T] and so on.

Then test undup/2:

1 ?- undup([1,1,1,2,3,4,4,5],L).
L = [_G2760, _G2808, _G2847, _G2877, _G2889] ;
false.

Clearly, not what you expect. The culprit should that anon var. Indeed, this works:

undup([], []).
undup([X|Xs], [X|B]) :- remove(X,Xs,K), undup(K, B).

2 ?- undup([1,1,1,2,3,4,4,5],L).
L = [1, 2, 3, 4, 5] ;
false.

Now, unite/3. First of all, is/2 is abused. It introduces arithmetic, then plain unification suffices here: X = S.

Then the base cases are hardcoded to work where lists' length differs at most by 1. Again, simpler code should work better:

unite([], [], []).
unite( X, [],  X).
unite([],  X,  X).
...

Also, note the first clause is useless, being already covered by (both) second and third clauses.