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

how append/3 work anonymous variable such 1 in example below:

append(_,[b(f,nd,p)|rest],visited). 

couldn't in fact use append/2?

thank answer!

the goal

..., append(_,[b(f,nd,p)|rest],visited). 

reads:

somewhere in list of visited nodes, there b(f, nd, p) subsequent nodes rest.

note there might more 1 such node, there cut @ place or once/1.

couldn't in fact use append/2?

where did dig out skeleton - er - library predicate? in fact, may permit implement append/3:

myappend(xs, ys, zs) :-    append([xs,ys], zs). 

so intuition behind list xs concatenated list ys list zs. declarative viewpoint, there no differences. or they?

at least procedurally, there are differences! ...

?- append([], ys, zs), false. false. 

... terminates, ...

?- append([[], ys], zs), false. **loops** 

... loops! (in swi , sicstus) let's see concrete answers produced (i'll use sicstus, because prints variables more compactly, swi uses hard-to-read variables _g1376):

| ?- append([], ys, zs). zs = ys ? ; no  | ?- 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 single answer, whereas append/2 seems produce infinitely many. how can declaratively equivalent, or not?

answers vs. solutions

first, let me point out ys = [], zs = [] above concrete solution. next answer ys = [_a], zs = [_a] contains infinitely many solutions. _a stands here infinitely many ground terms. there way collapse (or lift) infinitely many solutions single, elegant , finite answer.

now, append([], ys, zs) went step further, collapsed answers single one: ys = zs. but, right? answer means any term ys. in particular, say, non_list not list. think of it:

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

so append/3 did overgeneralize or lift things far. in fact, definition is:

append([], zs, zs). append([x|xs], ys, [x|zs]) :-    append(xs, ys, zs). 

the fact reads:

the empty list appended anything, (including polish kings), anything.

clearly fact states bit much. overgeneralization helped improve termination properties! and, if bit careful, overgeneralization never show. ((^{_{kind of shady deal?}}))

but then, prolog enjoys many other properties - in particular "single assignment" property of logic variables mitigates problem. same technique used difference lists , dcgs. if use consistently , wisely, improve performance , termination properties.