How does the predicate 'append/3' work with an anonymous variable in Prolog?

Question

How exactly does append/3 work with an anonymous variable such as the one in the example below:

append(_,[b(F,ND,P)|Rest],Visited).

Couldn't we in fact just use append/2?

Thank you for your answer!

Answer 1

The goal

..., append(_,[b(F,ND,P)|Rest],Visited).

reads:

Somewhere in the list of Visited nodes, there is a b(F, ND, P) with subsequent nodes Rest.

Note that there might be more than one such node, so most probably there is a cut at some place or a once/1.

Couldn't we in fact just use append/2?

Where did you dig out that skeleton - er - library predicate? But in fact, this may permit us to implement append/3:

myappend(Xs, Ys, Zs) :-
   append([Xs,Ys], Zs).

So the intuition behind is that list Xs concatenated with list Ys is list Zs. From this declarative viewpoint, there are clearly no differences. Or are they?

At least procedurally, there are differences! For ...

?- append([], Ys, Zs), false.
   false.

... terminates, but ...

?- append([[], Ys], Zs), false.
   loops.

... loops! (In SWI and SICStus) Let's see the concrete answers produced (I'll use SICStus, because it prints variables more compactly, SWI uses hard-to-read variables like _G1376):

?- append([], Ys, Zs).
   Zs = Ys.
?- append([[], Ys], Zs).
   Ys = [], Zs = []
;  Ys = [_A], Zs = [_A]
;  Ys = [_A,_B], Zs = [_A,_B]
;  Ys = [_A,_B,_C], Zs = [_A,_B,_C]
; ... .

So append/3 produced a single answer, whereas append/2 seems to produce infinitely many. How can they be declaratively equivalent, or are they not?

Answers vs. solutions

First, let me point out that Ys = [], Zs = [] above is a concrete solution. The next is the answer Ys = [_A], Zs = [_A] which contains infinitely many solutions. The _A stands here for infinitely many ground terms. So there is a way to collapse (or lift) infinitely many solutions into a single, elegant and finite answer.

Now, append([], Ys, Zs) went a step further, it collapsed all answers into a single one: Ys = Zs. But, is this right? This answer means that any term could be the Ys. In particular, say, non_list which is certainly not a list. Think of it:

?- append([a],nonlist,Zs).
   Zs = [a|nonlist].

So what append/3 effectively did was to overgeneralize or to lift things too far. In fact, its definition is:

append([], Zs, Zs).
append([X|Xs], Ys, [X|Zs]) :-
   append(Xs, Ys, Zs).

The fact reads:

The empty list appended with anything, really anything (including all Polish kings), is just that anything.

Clearly that fact states a bit too much. But it is this very overgeneralization that helped to improve termination properties! And, if we are a bit careful, this overgeneralization will never show. ((^{_{Kind of a shady deal?}}))

But then, Prolog enjoys many other properties - in particular the "single assignment" property of logic variables that mitigates this problem. The very same technique is used very often also for difference lists and DCGs. If you use it consistently and wisely, it will improve performance and termination properties.