Reversible merge

Question

We can combine the two sorted lists as follows

merge_([A|T], [], [A|T]).
merge_([], [A|T], [A|T]).
merge_([A|T], [B|U], [A|V]) :- A @< B, merge_(T, [B|U], V).
merge_([A|T], [B|U], [B|V]) :- A @>= B, merge_([A|T], U, V).

which works great in one direction. What does not work for this definition are queries like the following merge_(A, [a, b, c], [a, b, c, d])., although there is a unique and quite obvious solution A = [d].. Even an iteration over merge_(A, B, [a, b, c]).should give a rather trivial set of results: A- an ordered subset of [a, b, c]and B = [a, b, c] \ A.

How to change the definition merge_so that it works in all directions?

Answer 1

@mat . CLP (FD), ( " " ).

, A @< B A B , , "" . , , valid(X), X , valid(A), valid(B), A @< B, .... , , , , .

    valid(X) :- member(X, [a,b,c,d,e,f,g,h,i,j,k,l,m,n]).

    merge_([A|T], [], [A|T]).
    merge_([], [A|T], [A|T]).
    merge_([A|T], [B|U], [A|V]) :- valid(A), valid(B), A @< B, merge_(T, [B|U], V).
    merge_([A|T], [B|U], [B|V]) :- valid(A), valid(B), A @>= B, merge_([A|T], U, V).

, A B , " ":

| ?- merge_(A, [a, b, c], [a, b, c, d]).

A = [d] ? a

no
| ?- merge_(A, B, [a, b, c]).

A = [a,b,c]
B = [] ? a

A = []
B = [a,b,c]

A = [a]
B = [b,c]

A = [a,c]
B = [b]

A = [a,b]
B = [c]

A = [b,c]
B = [a]

A = [b]
B = [a,c]

A = [c]
B = [a,b]

no
| ?-

Answer 2

(@<)/2 (@>=)/2 , , , "" . , , , .

, :

, .

, , ,

?- Y @< X.
false.

, ? , X=1, Y=0 - , ? :

?- X=1, Y=0, Y @< X.
X = 1,
Y = 0.

Whaaat? , !

, . , , .

. , .

, , CLP (FD) :

merge_([A|T], [], [A|T]).
merge_([], [A|T], [A|T]).
merge_([A|T], [B|U], [A|V]) :- A #< B, merge_(T, [B|U], V).
merge_([A|T], [B|U], [B|V]) :- A #>= B, merge_([A|T], U, V).

, :

?- merge_(A, [1,2,3], [1,2,3,4]).
A = [4].

, , . : , , . , .

. , Prolog CLP (FD), .

, , , , , CLP (FD):

?- merge_(A, B, [1,2,3]).
A = [1, 2, 3],
B = [] ;
A = [],
B = [1, 2, 3] ;
A = [1],
B = [2, 3] ;
A = [1, 2],
B = [3] ;
etc.