Explanation for why append/3 produces infinite number of solutions in these cases

Question

I'm having trouble understanding this question about Prolog. The question is as follows:

Select all of the following goals that have an infinite number of solutions.

And here are the possible answers:

append([a,b,c,d], Y, Z)
append(X, Y, X)
append(X, [a,b,c,d], Z)
append(X, Y, [a,b,c,d])

Apparently the correct answers are 2 and 3, but I don't get why 1 isn't also correct - wouldn't there be infinite possibilities for Z and hence also Y? Also, why would 2 be correct, since the first argument and the third argument ("the result") are identical? Sounds like Y could just be [].

Thanks a lot!

Answer 1

append(X, Y, X) can only be true of Y == [] (that's a "theorem for free" à la Wadler) but under that constraint, X can be any of infinite set of possibilities:

SWI-Prolog finds out about Y == [] and is noncommittal about the content of the X list, giving it only as a list of unbound variables:

?- append(X,Y,X).
X = Y, Y = [] ;   % alternative writing of X = [], Y = []
X = [_6696],
Y = [] ;
X = [_6696, _7824],
Y = [] ;
X = [_6696, _7824, _8952],
Y = [] ;
X = [_6696, _7824, _8952, _10080],
Y = [] ;
X = [_6696, _7824, _8952, _10080, _11208],
Y = [] 
...

And you are correct that append([a,b,c,d], Y, Z) should be listed as admitting an infinite number of solutions.

Interestingly, SWI-Prolog does not enumerate templates / lists of placeholder variables / candidates in this case but spits out what is essentially a rewrite of the constraint append([a,b,c,d], Y, Z), i.e. it behaves more theorem-proverish than in case 1:

?- append([a,b,c,d],Y,Z).
Z = [a, b, c, d|Y].

(That's a Prolog ambiguity: When does it enumerate and when not? If there were a Prolog notation for "list of N values of unspecified content, N an integer between 0 and +oo" such a notation could be used as output of append(X,Y,X) instead.)

The alternative, not chosen here, would be:

?- append([a,b,c,d],Y,Z).
Y = [], 
Z = [a,b,c,d] ;
Y = [_1], 
Z = [a,b,c,d,_1] ;
Y = [_1,_2], 
Z = [a,b,c,d,_1,_2] ;
...

Are there any Prologs that do the above? There might be.