Explanation of a Prolog algorithm to append two lists together

First, let’s translate the clauses into something more understandable:

append([], List, List) :- !.

can be written

append([], List2, Result) :-
    Result = List2,
    !.

and

append([H|L1], List2, [H|L3]) :- append(L1, List2, L3).

can be written

append(List1, List2, Result) :-
    List1  = [Head1 | Tail1],
    Result = [HeadR | TailR],
    Head1  =  HeadR,
    append(Tail1, List2, TailR).

I hope this will already be clearer for you.

Then, step by step, the number indicates the clause used each time, and the resulting call is shown:

append([9, 2, 3, 4], [-10, -5, 6, 7, 8], Ot).
|
2
|
` append([2, 3, 4], [-10, -5, 6, 7, 8], Ot'). % and Ot = [9|Ot']
  |
  2
  |
  ` append([3, 4], [-10, -5, 6, 7, 8], Ot''). % and Ot' = [2|Ot'']
    |
    2
    |
    ` append([4], [-10, -5, 6, 7, 8], Ot'''). % and Ot'' = [3|Ot''']
      |
      2
      |
      ` append([], [-10, -5, 6, 7, 8], Ot''''). % and Ot''' = [4|Ot'''']
        |
        1
        |
        ` Ot'''' = [-10, -5, 6, 7, 8]

At this step all the values we’re interested in are already defined. Notice how the head of the result is set before its tail is filled up by a subsequent (tail recursive) call to append, building the resulting list in the characteristic for Prolog top-down fashion (also known as “tail recursion modulo cons”).

Let’s follow the definitions to see what Ot is, at the final step:

Ot = [9|Ot']
        Ot' = [2|Ot'']
                 Ot'' = [3|Ot''']
                           Ot''' = [4|Ot'''']
                                      Ot'''' = [-10, -5, 6, 7, 8]
                           Ot''' = [4,          -10, -5, 6, 7, 8]
                 Ot'' = [3,         4,          -10, -5, 6, 7, 8]
        Ot' = [2,        3,         4,          -10, -5, 6, 7, 8]
Ot = [9,       2,        3,         4,          -10, -5, 6, 7, 8]

I hope you’ll get something out of it.