Combining two lists in prolog

Question

How would you combine two lists? This is what I tried but it doesn't give me the result I want,

Y = [1,2,3].
Z = [3,4,5].
X = [Y,Z].

This just gives a bigger list with a divided Head and Tail.

I want my output to look like this:

X = [1,2,3,4,5].

Answer 1

If you want to combine two ground lists with a possible overlap into a third one keeping in the result only one copy of the overlap elements (i.e. the suffix elements of the first list which also form a prefix of the second), you can write it this way:

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

sample runs:

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

---

A slight modification to avoid using the cut:

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

Sample runs:

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

Answer 2

The question is completely unclear: Is it about merging sorted lists? Sorted lists of numbers, maybe? Is it about a kind of append that only keeps one copy of a shared suffix of the first list/prefix of the second list? Is it about dropping duplicates in some more general sense?

Here is a solution that drops the shared suffix/prefix. It is similar to slago's solution, except that it uses two predicates for the two different states that the computation can be in: merge "copies" elements from the first argument to the third argument; at some point it switches to mergerest, which "keeps copying" but requires that its first argument be a non-empty prefix of the second argument.

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

Using false's animal definitions:

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

Behavior on only the third argument being bound, for example:

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

More generally:

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

Fast failure:

?- merge([a|_],_,[b|_]).
false.