Prolog合并两个列表

Question

我需要在 Prolog 中合并两个列表。输入应该是谓词 merge/3.

应该像这样工作：

?- merge([6,4,b,8], [5,b,s,6], X).
X = [6, 4, b, 8, 5, s].

我尝试过的：

%rules
merge(A, B, X):- 
    merge(A, B, B, X).

merge([], X, _, X).
merge([Head|L1], [Head|L2], Tmp, [Head|X]) :-
    merge(L1, L2, Tmp, X),
    !.
merge(L1, [_|L2], Tmp, X) :-
    merge(L1, L2, Tmp, X),
    !.
merge([A|L1], [], Tmp, [A|X]) :-
    merge(L1, Tmp, Tmp, X),
    !.

我得到的：

?- merge([1,2,a,3], [5,d,a,1], X).
X = [1, 2, a, 3, 5, d, a, 1].

我的期望：

?- merge([1,2,a,3], [5,d,a,1], X).
X = [1, 2, a, 3, 5, d].

Answer 1

如果元素的顺序不以某种方式取决于两个输入列表的顺序，这是一个惯用的 Prolog 解决方案：

?- append([6,4,b,8], [5,b,s,6], A), sort(A, B).
A = [6, 4, b, 8, 5, b, s, 6],
B = [4, 5, 6, 8, b, s].

如果顺序很重要，您需要解释清楚。

以及对您显示的代码的一些评论。您为谓词选择的名称："join" 和 "merge" 都具有明确的含义 与您试图实现的目标不同 ("join" 如在关系数据库中，"merge" 如在 "merge two ordered lists" 中）。您正在做的是一个 "union"（顺便说一下，单击这个 link 并阅读代码！）。

此外，将 cut 作为子句主体的最后一个子目标几乎总是一个错误（不是错误，而是错误）。一个谓词有多个不明显相互排斥的子句（如 merge/4 的 4 个子句中的最后 3 个）通常是设计缺陷（不是错误）。

Answer 2

这可以通过重写内置谓词来完成！例如：

my_append([], R, R) .
my_append([H|T], R1, [H|R2]) :-
    my_append(T, R1, R2).


my_member(H, [H|_]).
my_member(H, [_|T]) :-
    my_member(H, T).

所以，我可以说将 L 与一个空列表合并得到这个列表 L

merge(L, [], L).

现在，要合并两个列表，我查看第二个列表的第一个元素。

如果它在第一个列表中，我将忽略它并将第一个列表与第二个列表的其余部分合并。

如果不是，我将第一个元素添加到第一个列表的末尾，并将新的第一个列表与第二个列表的其余部分合并。

不得不说效率不高！！

merge(L, [H| T], R) :-
    (   my_member(H, L)
    ->  merge(L, T, R)
    ;   my_append(L, [H], L1),
        merge(L1, T, R)).

Prolog合并两个列表

Prolog merge two lists

recursion

merge

list

prolog