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