在序言中组合两个列表
Combining two lists in prolog
你会如何合并两个列表？这是我尝试过的，但没有给我想要的结果，
Y = [1,2,3].
Z = [3,4,5].
X = [Y,Z].
这只是给出了一个更大的列表，其中包含分开的头和尾。
我希望我的输出看起来像这样：
X = [1,2,3,4,5].
实际上 prolog 并不是这样工作的（你所做的并不是你想象的赋值）。
但无论如何，这是附加两个列表的方法：
?- append([1,2,3],[3,4,5],X).
returns: X = [1, 2, 3, 3, 4, 5].
如果你想将两个可能重叠的基础列表组合成第三个，结果只保留重叠元素的一个副本（即第一个列表的后缀元素也构成第二个列表的前缀） ，你可以这样写：
combine(A, B, C):-
append(A1, Common, A),
append(Common, B1, B),
!, % The cut here is to keep the longest common sub-list
append([A1, Common, B1], C).
样本运行：
?- combine([1,2,3],[3,4,5], C).
C = [1, 2, 3, 4, 5].
?- combine([1,2,3,4],[3,4,5], C).
C = [1, 2, 3, 4, 5].
略作修改以避免使用剪切：
combine(A, B, C):-
append(A1, Common, A),
append(Common, B1, B),
bagof(NotCommonA-NotCommonB,
not_common(A1, B1, NotCommonA, NotCommonB),
LDifs),
maplist(difpair, LDifs),
append([A1, Common, B1], C).
not_common(L, R, [ItemA|NotCommonA], NotCommonB):-
append(_, [ItemA|NotCommonA], L),
length([ItemA|NotCommonA], LNotCommon),
length(NotCommonB, LNotCommon),
append(NotCommonB, _, R).
difpair(L-R):-
dif(L, R).
样本运行：
?- combine([1,2,3],[3,4,5], C).
C = [1, 2, 3, 4, 5] ;
false.
?- combine([1,2,3,X],[3,4,5], C).
X = 4,
C = [1, 2, 3, 4, 5] ;
X = 3,
C = [1, 2, 3, 3, 4, 5] ;
C = [1, 2, 3, X, 3, 4, 5],
dif(X, 3),
dif(X, 4) ;
;
false
一个可能的解决方案是：
combine([], B, B).
combine(A, [], A).
combine([X|A], [X|B], [X|C]) :- combine(A, B, C).
combine([X|A], [Y|B], [X|C]) :- dif(X,Y), combine(A, [Y|B], C).
一些查询：
?- combine([1,2,3,4,5], [3,4,5,6,7], C).
C = [1, 2, 3, 4, 5, 6, 7] ;
false.
?- combine([1,2,3,4,5], [4,5,6,7], C).
C = [1, 2, 3, 4, 5, 6, 7] ;
false.
?- combine([1,2,3,4,5], [5,6,7], C).
C = [1, 2, 3, 4, 5, 6, 7] ;
false.
?- combine([1,2,3,4,5], [6,7], C).
C = [1, 2, 3, 4, 5, 6, 7] ;
false.
?- combine([1,2,3,4,5], [], C).
C = [1, 2, 3, 4, 5] ;
false.
?- combine([], [3,4,5,6,7], C).
C = [3, 4, 5, 6, 7] ;
false.
这是一个测试程序（源自 Meloni，1976 年），经过简化以避免转换和琐碎的解决方案。请参阅答案替换中 and printing chars as double quoted strings 的定义。
:- set_prolog_flag(double_quotes, chars).
animal("alligator").
animal("tortue").
animal("caribou").
animal("ours").
animal("cheval").
animal("vache").
animal("lapin").
% animal("iguana").
% animal("anaconda").
mutation(C) :-
animal(A),
animal(B),
dif(A, C),
combine(A, B, C),
iwhen(ground(A+B+C), \+ append(A, B, C) ).
?- mutation(C).
C = "alligatortue"
; C = "caribours"
; C = "chevalligator"
; C = "chevalapin"
; C = "vacheval"
; false.
问题完全不清楚：是关于合并排序列表吗？排序的数字列表，也许？它是关于一种仅保留第二个列表的第一个 list/prefix 的共享后缀的副本的附加吗？是关于删除更一般意义上的重复项吗？
这是一个删除共享 suffix/prefix 的解决方案。它类似于 slago 的解决方案，除了它使用两个谓词来表示计算可能处于的两种不同状态： merge 将元素从第一个参数“复制”到第三个参数；在某些时候它切换到 mergerest，它“继续复制”但要求它的第一个参数是第二个参数的非空前缀。
merge(Xs, Ys, Zs) :-
mergerest(Xs, Ys, Zs).
merge([X|Xs], [Y|Ys], [X|Zs]) :-
merge(Xs, [Y|Ys], Zs).
mergerest([X], [X|Ys], [X|Ys]).
mergerest([X|Xs], [X|Ys], [X|Zs]) :-
mergerest(Xs, Ys, Zs).
使用 false 的动物定义：
?- animal(A), animal(B), dif(A, Mutation), merge(A, B, Mutation).
A = [a,l,l,i,g,a,t,o,r],
B = [t,o,r,t,u,e],
Mutation = [a,l,l,i,g,a,t,o,r,t,u,e] ;
A = [c,a,r,i,b,o,u],
B = [o,u,r,s],
Mutation = [c,a,r,i,b,o,u,r,s] ;
A = [c,h,e,v,a,l],
B = [a,l,l,i,g,a,t,o,r],
Mutation = [c,h,e,v,a,l,l,i,g,a,t,o,r] ;
A = [c,h,e,v,a,l],
B = [l,a,p,i,n],
Mutation = [c,h,e,v,a,l,a,p,i,n] ;
A = [v,a,c,h,e],
B = [c,h,e,v,a,l],
Mutation = [v,a,c,h,e,v,a,l] ;
false.
仅绑定第三个参数的行为，例如：
?- merge(Xs, Ys, [1, 2, 3]).
Xs = [1],
Ys = [1, 2, 3] ;
Xs = [1, 2],
Ys = [1, 2, 3] ;
Xs = Ys, Ys = [1, 2, 3] ;
Xs = [1, 2],
Ys = [2, 3] ;
Xs = [1, 2, 3],
Ys = [2, 3] ;
Xs = [1, 2, 3],
Ys = [3] ;
false.
更一般地说：
?- length(Zs,_), merge(Xs, Ys, Zs).
Zs = Xs, Xs = Ys, Ys = [_4262] ;
Zs = Ys, Ys = [_4262, _4268],
Xs = [_4262] ;
Zs = Xs, Xs = Ys, Ys = [_4262, _4268] ;
Zs = Xs, Xs = [_4262, _4268],
Ys = [_4268] ;
Zs = Ys, Ys = [_4262, _4268, _4274],
Xs = [_4262] ;
Zs = Ys, Ys = [_4262, _4268, _4274],
Xs = [_4262, _4268] ;
Zs = Xs, Xs = Ys, Ys = [_4262, _4268, _4274] ;
Zs = [_4262, _4268, _4274],
Xs = [_4262, _4268],
Ys = [_4268, _4274] ;
Zs = Xs, Xs = [_4262, _4268, _4274],
Ys = [_4268, _4274] ;
Zs = Xs, Xs = [_4262, _4268, _4274],
Ys = [_4274] ;
Zs = Ys, Ys = [_4262, _4268, _4274, _4280],
Xs = [_4262] ;
Zs = Ys, Ys = [_4262, _4268, _4274, _4280],
Xs = [_4262, _4268] . % ad nauseam
快速失败：
?- merge([a|_],_,[b|_]).
false.
这是对这个问题的另一种看法：
combine([A|As], [B|Bs], [A|Cs]):-
dif(A, B),
combine(As, [B|Bs], Cs).
combine(As, Bs, Cs):-
suffix_prefix(As, Bs, Cs).
combine([A|As], [A|Bs], [A|Cs]):-
not_suffix_prefix(As, Bs, Cs),
combine(As, [A|Bs], Cs).
suffix_prefix([], Bs, Bs).
suffix_prefix([A|As], [A|Bs], [A|Cs]):-
suffix_prefix(As, Bs, Cs).
not_suffix_prefix([_|_], [], [_|_]).
not_suffix_prefix([A|As], [A|Bs], [_|Cs]):-
not_suffix_prefix(As, Bs, Cs).
not_suffix_prefix([A|_], [B|_], _):-
dif(A, B).
样本运行（来自测试答案），combine([a|_], _, [b|_]) 失败，生成所有解决方案和一些其他测试：
?- mutation(C).
C = [a, l, l, i, g, a, t, o, r, t, u, e] ;
C = [c, a, r, i, b, o, u, r, s] ;
C = [c, h, e, v, a, l, l, i, g, a, t, o, r] ;
C = [c, h, e, v, a, l, a, p, i, n] ;
C = [v, a, c, h, e, v, a, l] ;
false.
?- combine([a|_], _, [b|_]).
false.
?- combine([1,2,3], [3,4,5], Cs).
Cs = [1, 2, 3, 4, 5] ;
false.
?- combine([1,2,3,X], [3,4,5], Cs).
X = 4,
Cs = [1, 2, 3, 4, 5] ;
Cs = [1, 2, 3, '$VAR'('X'), 3, 4, 5],
dif('$VAR'('X'), 3),
dif('$VAR'('X'), 4) ;
;
X = 3,
Cs = [1, 2, 3, 3, 4, 5] ;
false.
?- combine([A,A], [A], C).
C = ['$VAR'('A'), '$VAR'('A')] ;
false.
?- length(Zs, Len), combine(Xs, Ys, Zs).
Zs = Xs, Xs = Ys, Ys = [],
Len = 0 ;
Zs = Ys, Ys = [_2419916],
Len = 1,
Xs = [] ;
Zs = Xs, Xs = Ys, Ys = [_2419916],
Len = 1 ;
Zs = [_2420492, _2420498],
Len = 2,
Xs = [_2420492],
Ys = [_2420498],
dif(_2420492, _2420498) ;
;
Zs = Xs, Xs = [_2420498, _2420504],
Len = 2,
Ys = [_2420504],
dif(_2420498, _2420504) ;
;
Zs = Ys, Ys = [_2419916, _2419922],
Len = 2,
Xs = [] ;
Zs = Ys, Ys = [_2419916, _2419922],
Len = 2,
Xs = [_2419916] ;
Zs = Xs, Xs = Ys, Ys = [_2419916, _2419922],
Len = 2 ;
Zs = Xs, Xs = [_2419916, _2419916],
Len = 2,
Ys = [_2419916] ;
Zs = [_2420690, _2420696, _2420702],
Len = 3,
Xs = [_2420690, _2420696],
Ys = [_2420702],
dif(_2420690, _2420702),
dif(_2420696, _2420702) ;
.... continues ...
这是另一个解决方案，与 gusbro 的解决方案比较相似，但修复了一些遗漏的情况（例如 combine([A,A],[A],C) 应该成功 C=[A,A]）。
% Third is the concatenation of First and Second but without the longest suffix
combine(As,Bs,Bs):- % of First that is also a prefix of Second
prefix(As,Bs).
combine([A|As],Bs,[A|Cs]):-
prefix(As, Cs), % Necessary when As is var to avoid
not_prefix([A|As], Bs), % generating too long lists
combine(As,Bs,Cs).
% First is prefix of Second
prefix([],_).
prefix([A|As],[A|Bs]):-
prefix(As,Bs).
% First is not prefix of Second
not_prefix(As,Bs):-
longer(As,Bs).
not_prefix(As,Bs):-
not_longer(As,Bs),
not_prefix2(As,Bs).
% First is not prefix of Second, knowing it is not longer
not_prefix2([A|As],[A|Bs]):-
not_prefix2(As,Bs).
not_prefix2([A|_],[B|_]):-
dif(A,B).
% First is longer than Second
longer([_|_], []).
longer([_|As],[_|Bs]):-
longer(As,Bs).
% First is not longer than Second
not_longer([], _).
not_longer([_|As],[_|Bs]):-
not_longer(As,Bs).
一些测试：
?- combine([1,2,3], [3,4,5], Cs).
Cs = [1,2,3,4,5] ? ;
no
?- combine([1,2,3,X], [3,4,5], Cs).
X = 4,
Cs = [1,2,3,4,5] ? ;
X = 3,
Cs = [1,2,3,3,4,5] ? ;
Cs = [1,2,3,X,3,4,5],
prolog:dif(X,4),
prolog:dif(X,3) ? ;
no
?- combine([a|_], _, [b|_]).
no
?- length(Cs, Len), combine(As, Bs, Cs).
Cs = [],
Len = 0,
As = [],
Bs = [] ? ;
Cs = [_A],
Len = 1,
As = [],
Bs = [_A] ? ;
Cs = [_A],
Len = 1,
As = [_A],
Bs = [_A] ? ;
Cs = [_A],
Len = 1,
As = [_A],
Bs = [] ? ;
Cs = [_A,_B],
Len = 2,
As = [],
Bs = [_A,_B] ? ;
Cs = [_A,_B],
Len = 2,
As = [_A],
Bs = [_A,_B] ? ;
Cs = [_A,_B],
Len = 2,
As = [_A,_B],
Bs = [_A,_B] ? ;
Cs = [_A,_B],
Len = 2,
As = [_A],
Bs = [_B],
prolog:dif(_A,_B) ? ;
Cs = [_A,_B],
Len = 2,
As = [_A,_B],
Bs = [] ? ;
Cs = [_A,_B],
Len = 2,
As = [_A,_B],
Bs = [_B] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [],
Bs = [_A,_B,_C] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A],
Bs = [_A,_B,_C] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B],
Bs = [_A,_B,_C] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B,_C],
Bs = [_A,_B,_C] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A],
Bs = [_B,_C],
prolog:dif(_A,_B) ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B],
Bs = [_C],
prolog:dif(_B,_C) ? ;
Cs = [_A,_A,_B],
Len = 3,
As = [_A,_A],
Bs = [_A,_B],
prolog:dif(_A,_B) ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B],
Bs = [_B,_C],
prolog:dif(_A,_B) ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B,_C],
Bs = [] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B,_C],
Bs = [_C] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B,_C],
Bs = [_B,_C] ? ;
Cs = [_A,_B,_C,_D],
Len = 4,
As = [],
Bs = [_A,_B,_C,_D] ?
yes
你会如何合并两个列表？这是我尝试过的，但没有给我想要的结果，
Y = [1,2,3].
Z = [3,4,5].
X = [Y,Z].
这只是给出了一个更大的列表，其中包含分开的头和尾。
我希望我的输出看起来像这样：
X = [1,2,3,4,5].
实际上 prolog 并不是这样工作的（你所做的并不是你想象的赋值）。
但无论如何，这是附加两个列表的方法：
?- append([1,2,3],[3,4,5],X).
returns: X = [1, 2, 3, 3, 4, 5].
如果你想将两个可能重叠的基础列表组合成第三个，结果只保留重叠元素的一个副本（即第一个列表的后缀元素也构成第二个列表的前缀） ，你可以这样写：
combine(A, B, C):-
append(A1, Common, A),
append(Common, B1, B),
!, % The cut here is to keep the longest common sub-list
append([A1, Common, B1], C).
样本运行：
?- combine([1,2,3],[3,4,5], C).
C = [1, 2, 3, 4, 5].
?- combine([1,2,3,4],[3,4,5], C).
C = [1, 2, 3, 4, 5].
略作修改以避免使用剪切：
combine(A, B, C):-
append(A1, Common, A),
append(Common, B1, B),
bagof(NotCommonA-NotCommonB,
not_common(A1, B1, NotCommonA, NotCommonB),
LDifs),
maplist(difpair, LDifs),
append([A1, Common, B1], C).
not_common(L, R, [ItemA|NotCommonA], NotCommonB):-
append(_, [ItemA|NotCommonA], L),
length([ItemA|NotCommonA], LNotCommon),
length(NotCommonB, LNotCommon),
append(NotCommonB, _, R).
difpair(L-R):-
dif(L, R).
样本运行：
?- combine([1,2,3],[3,4,5], C).
C = [1, 2, 3, 4, 5] ;
false.
?- combine([1,2,3,X],[3,4,5], C).
X = 4,
C = [1, 2, 3, 4, 5] ;
X = 3,
C = [1, 2, 3, 3, 4, 5] ;
C = [1, 2, 3, X, 3, 4, 5],
dif(X, 3),
dif(X, 4) ;
;
false
一个可能的解决方案是：
combine([], B, B).
combine(A, [], A).
combine([X|A], [X|B], [X|C]) :- combine(A, B, C).
combine([X|A], [Y|B], [X|C]) :- dif(X,Y), combine(A, [Y|B], C).
一些查询：
?- combine([1,2,3,4,5], [3,4,5,6,7], C).
C = [1, 2, 3, 4, 5, 6, 7] ;
false.
?- combine([1,2,3,4,5], [4,5,6,7], C).
C = [1, 2, 3, 4, 5, 6, 7] ;
false.
?- combine([1,2,3,4,5], [5,6,7], C).
C = [1, 2, 3, 4, 5, 6, 7] ;
false.
?- combine([1,2,3,4,5], [6,7], C).
C = [1, 2, 3, 4, 5, 6, 7] ;
false.
?- combine([1,2,3,4,5], [], C).
C = [1, 2, 3, 4, 5] ;
false.
?- combine([], [3,4,5,6,7], C).
C = [3, 4, 5, 6, 7] ;
false.
这是一个测试程序（源自 Meloni，1976 年），经过简化以避免转换和琐碎的解决方案。请参阅答案替换中
:- set_prolog_flag(double_quotes, chars).
animal("alligator").
animal("tortue").
animal("caribou").
animal("ours").
animal("cheval").
animal("vache").
animal("lapin").
% animal("iguana").
% animal("anaconda").
mutation(C) :-
animal(A),
animal(B),
dif(A, C),
combine(A, B, C),
iwhen(ground(A+B+C), \+ append(A, B, C) ).
?- mutation(C).
C = "alligatortue"
; C = "caribours"
; C = "chevalligator"
; C = "chevalapin"
; C = "vacheval"
; false.
问题完全不清楚：是关于合并排序列表吗？排序的数字列表，也许？它是关于一种仅保留第二个列表的第一个 list/prefix 的共享后缀的副本的附加吗？是关于删除更一般意义上的重复项吗？
这是一个删除共享 suffix/prefix 的解决方案。它类似于 slago 的解决方案，除了它使用两个谓词来表示计算可能处于的两种不同状态： merge 将元素从第一个参数“复制”到第三个参数；在某些时候它切换到 mergerest，它“继续复制”但要求它的第一个参数是第二个参数的非空前缀。
merge(Xs, Ys, Zs) :-
mergerest(Xs, Ys, Zs).
merge([X|Xs], [Y|Ys], [X|Zs]) :-
merge(Xs, [Y|Ys], Zs).
mergerest([X], [X|Ys], [X|Ys]).
mergerest([X|Xs], [X|Ys], [X|Zs]) :-
mergerest(Xs, Ys, Zs).
使用 false 的动物定义：
?- animal(A), animal(B), dif(A, Mutation), merge(A, B, Mutation).
A = [a,l,l,i,g,a,t,o,r],
B = [t,o,r,t,u,e],
Mutation = [a,l,l,i,g,a,t,o,r,t,u,e] ;
A = [c,a,r,i,b,o,u],
B = [o,u,r,s],
Mutation = [c,a,r,i,b,o,u,r,s] ;
A = [c,h,e,v,a,l],
B = [a,l,l,i,g,a,t,o,r],
Mutation = [c,h,e,v,a,l,l,i,g,a,t,o,r] ;
A = [c,h,e,v,a,l],
B = [l,a,p,i,n],
Mutation = [c,h,e,v,a,l,a,p,i,n] ;
A = [v,a,c,h,e],
B = [c,h,e,v,a,l],
Mutation = [v,a,c,h,e,v,a,l] ;
false.
仅绑定第三个参数的行为，例如：
?- merge(Xs, Ys, [1, 2, 3]).
Xs = [1],
Ys = [1, 2, 3] ;
Xs = [1, 2],
Ys = [1, 2, 3] ;
Xs = Ys, Ys = [1, 2, 3] ;
Xs = [1, 2],
Ys = [2, 3] ;
Xs = [1, 2, 3],
Ys = [2, 3] ;
Xs = [1, 2, 3],
Ys = [3] ;
false.
更一般地说：
?- length(Zs,_), merge(Xs, Ys, Zs).
Zs = Xs, Xs = Ys, Ys = [_4262] ;
Zs = Ys, Ys = [_4262, _4268],
Xs = [_4262] ;
Zs = Xs, Xs = Ys, Ys = [_4262, _4268] ;
Zs = Xs, Xs = [_4262, _4268],
Ys = [_4268] ;
Zs = Ys, Ys = [_4262, _4268, _4274],
Xs = [_4262] ;
Zs = Ys, Ys = [_4262, _4268, _4274],
Xs = [_4262, _4268] ;
Zs = Xs, Xs = Ys, Ys = [_4262, _4268, _4274] ;
Zs = [_4262, _4268, _4274],
Xs = [_4262, _4268],
Ys = [_4268, _4274] ;
Zs = Xs, Xs = [_4262, _4268, _4274],
Ys = [_4268, _4274] ;
Zs = Xs, Xs = [_4262, _4268, _4274],
Ys = [_4274] ;
Zs = Ys, Ys = [_4262, _4268, _4274, _4280],
Xs = [_4262] ;
Zs = Ys, Ys = [_4262, _4268, _4274, _4280],
Xs = [_4262, _4268] . % ad nauseam
快速失败：
?- merge([a|_],_,[b|_]).
false.
这是对这个问题的另一种看法：
combine([A|As], [B|Bs], [A|Cs]):-
dif(A, B),
combine(As, [B|Bs], Cs).
combine(As, Bs, Cs):-
suffix_prefix(As, Bs, Cs).
combine([A|As], [A|Bs], [A|Cs]):-
not_suffix_prefix(As, Bs, Cs),
combine(As, [A|Bs], Cs).
suffix_prefix([], Bs, Bs).
suffix_prefix([A|As], [A|Bs], [A|Cs]):-
suffix_prefix(As, Bs, Cs).
not_suffix_prefix([_|_], [], [_|_]).
not_suffix_prefix([A|As], [A|Bs], [_|Cs]):-
not_suffix_prefix(As, Bs, Cs).
not_suffix_prefix([A|_], [B|_], _):-
dif(A, B).
样本运行（来自测试答案），combine([a|_], _, [b|_]) 失败，生成所有解决方案和一些其他测试：
?- mutation(C).
C = [a, l, l, i, g, a, t, o, r, t, u, e] ;
C = [c, a, r, i, b, o, u, r, s] ;
C = [c, h, e, v, a, l, l, i, g, a, t, o, r] ;
C = [c, h, e, v, a, l, a, p, i, n] ;
C = [v, a, c, h, e, v, a, l] ;
false.
?- combine([a|_], _, [b|_]).
false.
?- combine([1,2,3], [3,4,5], Cs).
Cs = [1, 2, 3, 4, 5] ;
false.
?- combine([1,2,3,X], [3,4,5], Cs).
X = 4,
Cs = [1, 2, 3, 4, 5] ;
Cs = [1, 2, 3, '$VAR'('X'), 3, 4, 5],
dif('$VAR'('X'), 3),
dif('$VAR'('X'), 4) ;
;
X = 3,
Cs = [1, 2, 3, 3, 4, 5] ;
false.
?- combine([A,A], [A], C).
C = ['$VAR'('A'), '$VAR'('A')] ;
false.
?- length(Zs, Len), combine(Xs, Ys, Zs).
Zs = Xs, Xs = Ys, Ys = [],
Len = 0 ;
Zs = Ys, Ys = [_2419916],
Len = 1,
Xs = [] ;
Zs = Xs, Xs = Ys, Ys = [_2419916],
Len = 1 ;
Zs = [_2420492, _2420498],
Len = 2,
Xs = [_2420492],
Ys = [_2420498],
dif(_2420492, _2420498) ;
;
Zs = Xs, Xs = [_2420498, _2420504],
Len = 2,
Ys = [_2420504],
dif(_2420498, _2420504) ;
;
Zs = Ys, Ys = [_2419916, _2419922],
Len = 2,
Xs = [] ;
Zs = Ys, Ys = [_2419916, _2419922],
Len = 2,
Xs = [_2419916] ;
Zs = Xs, Xs = Ys, Ys = [_2419916, _2419922],
Len = 2 ;
Zs = Xs, Xs = [_2419916, _2419916],
Len = 2,
Ys = [_2419916] ;
Zs = [_2420690, _2420696, _2420702],
Len = 3,
Xs = [_2420690, _2420696],
Ys = [_2420702],
dif(_2420690, _2420702),
dif(_2420696, _2420702) ;
.... continues ...
这是另一个解决方案，与 gusbro 的解决方案比较相似，但修复了一些遗漏的情况（例如 combine([A,A],[A],C) 应该成功 C=[A,A]）。
% Third is the concatenation of First and Second but without the longest suffix
combine(As,Bs,Bs):- % of First that is also a prefix of Second
prefix(As,Bs).
combine([A|As],Bs,[A|Cs]):-
prefix(As, Cs), % Necessary when As is var to avoid
not_prefix([A|As], Bs), % generating too long lists
combine(As,Bs,Cs).
% First is prefix of Second
prefix([],_).
prefix([A|As],[A|Bs]):-
prefix(As,Bs).
% First is not prefix of Second
not_prefix(As,Bs):-
longer(As,Bs).
not_prefix(As,Bs):-
not_longer(As,Bs),
not_prefix2(As,Bs).
% First is not prefix of Second, knowing it is not longer
not_prefix2([A|As],[A|Bs]):-
not_prefix2(As,Bs).
not_prefix2([A|_],[B|_]):-
dif(A,B).
% First is longer than Second
longer([_|_], []).
longer([_|As],[_|Bs]):-
longer(As,Bs).
% First is not longer than Second
not_longer([], _).
not_longer([_|As],[_|Bs]):-
not_longer(As,Bs).
一些测试：
?- combine([1,2,3], [3,4,5], Cs).
Cs = [1,2,3,4,5] ? ;
no
?- combine([1,2,3,X], [3,4,5], Cs).
X = 4,
Cs = [1,2,3,4,5] ? ;
X = 3,
Cs = [1,2,3,3,4,5] ? ;
Cs = [1,2,3,X,3,4,5],
prolog:dif(X,4),
prolog:dif(X,3) ? ;
no
?- combine([a|_], _, [b|_]).
no
?- length(Cs, Len), combine(As, Bs, Cs).
Cs = [],
Len = 0,
As = [],
Bs = [] ? ;
Cs = [_A],
Len = 1,
As = [],
Bs = [_A] ? ;
Cs = [_A],
Len = 1,
As = [_A],
Bs = [_A] ? ;
Cs = [_A],
Len = 1,
As = [_A],
Bs = [] ? ;
Cs = [_A,_B],
Len = 2,
As = [],
Bs = [_A,_B] ? ;
Cs = [_A,_B],
Len = 2,
As = [_A],
Bs = [_A,_B] ? ;
Cs = [_A,_B],
Len = 2,
As = [_A,_B],
Bs = [_A,_B] ? ;
Cs = [_A,_B],
Len = 2,
As = [_A],
Bs = [_B],
prolog:dif(_A,_B) ? ;
Cs = [_A,_B],
Len = 2,
As = [_A,_B],
Bs = [] ? ;
Cs = [_A,_B],
Len = 2,
As = [_A,_B],
Bs = [_B] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [],
Bs = [_A,_B,_C] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A],
Bs = [_A,_B,_C] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B],
Bs = [_A,_B,_C] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B,_C],
Bs = [_A,_B,_C] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A],
Bs = [_B,_C],
prolog:dif(_A,_B) ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B],
Bs = [_C],
prolog:dif(_B,_C) ? ;
Cs = [_A,_A,_B],
Len = 3,
As = [_A,_A],
Bs = [_A,_B],
prolog:dif(_A,_B) ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B],
Bs = [_B,_C],
prolog:dif(_A,_B) ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B,_C],
Bs = [] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B,_C],
Bs = [_C] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B,_C],
Bs = [_B,_C] ? ;
Cs = [_A,_B,_C,_D],
Len = 4,
As = [],
Bs = [_A,_B,_C,_D] ?
yes