Require help understanding a prolog method for appending list elements

append([],Xs,Xs).
append([Head|Tail],List2,[Head|Tail2]):-
    append(Tail,List2,Tail2).

The upper append method adds elements from first two parameter slots to the third param variable.

?-append([2,1], [3,4], X).
?-X=[2,1,3,4]

The way I see it in steps is (which is propably wrong):

1. append(2 | [1], [3,4], 2 | X)
2. append([1开发者_如何学编程], [3,4], X)
3. append(1 | [], [3,4], 1 | X)
4. append([], [3,4], [3,4])

And that's it. I can't wrap my head around how it adds together the elements and that's what i could use help with - a clear explanation on how this method works. I just don't understand how the [2,1] array gets added to the final result.

the X in the recursion is not the same X as in the original call if you rename it in the trace you'll see

append(2 | [1], [3,4], 2 | X1) -- X = [2|X1]

append([1], [3,4], X1)

append(1 | [], [3,4], 1 | X2) -- X1 = [1|X2]
append ([], [3,4], [3,4])  -- X2 = [3,4]

so X1 = [1,3,4] and X = [2,1,3,4]

First, you have to understand how a list is implemented in Prolog. It is an essentially recursive data structure.

• The empty list is a list of zero items, represented by the atom [].

• Non-empty lists are represented by the structure ./2, consisting of the head of the list (a prolog term), and the tail of the list (another list, consisting of all items save the first). So...

  • [] — a list of zero items, is represented as
    []
  • [a] — a list of 1 item, is represented as
    .(a,[])
  • [a,b] — a list of 2 items, is represented as
    .(a,.(b,[]))
  • [a,b,c] — a list of 3 items, is represented as
    .(a,.(b,.(c,[])))

The standard list notation using square brackets is just syntactic sugar on top of this representation. Saying [Head|Tail] is a polite way of saying .(Head,Tail) and saying [X,Y,Z|More] is the polite way of saying .(X,.(Y,.(Z,More))). (You might be noticing a certain....Lisp-ishness...to the internal list notation here.)

Understanding how a list is represented, the naive algorithm for appending (concatenating) one list to another is this:

First, there are two special cases to consider:

• The result of appending a non-empty list X to an empty list Y is X.
  Append [1,2,3] to [] and get [1,2,3].Note. This case is can be (is normally) handled by the ordinary case below, though. It's an opportunity for optimization as there's no point in recursing down the entire list, just to replace [] with [] at the end, right?.

• The result of appending an empty list X to a non-empty list Y is Y.
  Append [] to [1,2,3] and you get [1,2,3].

Otherwise, we have the ordinary case:

• Append non-empty list Y to non-empty list X to produce list Z. To do this is trivial:

  We simply recurse down on list X, popping its head as we go and and prepending that to list Z, the result. You'll notice that as this happens, list Z is a broken list structure, since its last node is always unbound rather than being []. This gets fixed at the very end when the source list, list X, is exhausted and degenerates into the special case of being an empty list. At that point, the unbound last node gets bound as it unifies with list Y (a list of zero or more nodes), leaving us with a correct list structure.

The Prolog code for append/3 expresses this algorithm directly. As noted earlier, the first clause is an optional optimization, as that can be handled by the 3rd clause (the ordinary case). It wants a cut, though, as without, backtracking would produce two solutions.

append( X      , [] , X      ) :- !. ; concatenate empty list X to list Y producing Y
append( []     , Y  , Y      ).      ; concatenate list X to empty list Y producing X
append( [X|Xs] , Y  , [X|Zs] ) :-    ; anything else
  append( Xs , Y , Zs )
  .