Reversible merge

Question

We can merge 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 fine in one direction. What doesn't work for this definition are queries like following merge_(A, [a, b, c], [a, b, c, d])., although there's unique and quite obvious solution A = [d].. Even iterating over merge_(A, B, [a, b, c]). should produce fairly trivial set of results: A being ordered subset of [a, b, c] and B = [a, b, c] \ A.

How do I change the definition of merge_ to make it work in all directions?

Answer 1

The predicates (@<)/2 and (@>=)/2 are not monotonic, and as such do not exhibit the properties that are necessary to correctly describe what "merging" means in general. Programs that use such predicates may work in particular instances, but will typically yield incorrect results in general.

To show you the essence of the problem, the following important declarative property is violated by these predicates:

Adding a goal can at most reduce, never extend, the set of solutions.

This monotonicity is broken by these properties, as illustrated for example with:

?- Y @< X.
false.

No solution exists, yes? In particular, certainly X=1, Y=0 is not a solution, right? Well let's see:

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

Whaaat? We were just told that there is no solution whatsoever!

In other words, we simply cannot apply even the most fundamental logical reasoning when working with these predicates. In my view, it is therefore best to avoid such predicates if you want to enjoy the benefits of logic programming to their fullest potential.

Constraints provide a way out of this mess. Constraints work correctly in all instantiation patterns, and allow for more general programs that work in all directions.

Here is a program that describes such merging of lists of integers, using CLP(FD) constraints:

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

The integer analogon of the example you cite:

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

So, this works exactly as expected. The only drawback: It requires that we map the entitites we want to reason about to integers. In practice, very many programs do reason over integers in any case, so that is often acceptable.

Similar generalizations are possible also for other domains. However, integers are among the most commonly used domains, and all widely used Prolog systems therefore ship with CLP(FD) constraints which I recommend as a useful starting point or even solution for such issues.

By the way, the other example you cite also works completely as expected if you simply use CLP(FD) constraints:

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