list - 可逆合并

我们可以按如下方式合并两个排序列表

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, [a, b, c], [a, b, c, d]). 之后的查询，尽管有一个独特且非常明显的解决方案 A = [d]. 。即使迭代 merge_(A, B, [a, b, c]). 也应该产生相当简单的结果集:A 是 [a, b, c] 和 B = [a, b, c] \ A 的有序子集。

如何更改 merge_ 的定义以使其适用于所有方向？

最佳答案

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

关于list - 可逆合并，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38587088/