Explanation of a Prolog algorithm to append two lists together

Question

This is an algorithm to append together two lists:

Domains
list= integer*

Predicates
nondeterm append(list, list, list)

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

Goal
append([9,2,3,4], [-10,-5,6,7,8], Ot).

The result is a list [9,2,3,4,-10,-5,6,7,8], and it's saved in "Ot".

My question is, how does this work?

What I understand is that in every recursive call, in the first list, you get only the tail as a list ( thus reducing its size by 1 until it's [] ), the second argument "List2" does not change at all, and the 3rd argument ... at first it's [], and after each recursive call you get its tail, but since it's [], it stays [].

So how come, suddenly, in 3rd argument ("Ot") we have the appended list ? Can someone explain this algorithm step by step ?

Digastric

Answer 1

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.

Tartuffery

The edit was a nice adition :) , i understand it now , what i was missing is that the head of List1 was being added to the tail of List3, thank you again , a great explanation. – Digastric

@Digastric if the two lines in the Mog's rewrite of the 2nd clause were exchanged, then you could say that the head of List1 was being added onto the tail of List3. But as it stands now the order is reversed. The head is set before the tail is filled up by a subsequent call to append, which is thus tail recursive modulo cons. – Repugn

Answer 2

Let's translate from Prolog into English. We have two rules:

1. The result of appending any List to [] is that List.

2. The result of appending any List to a list whose first element is H and remainder is L1 is equal to a list whose first element is also H whose remainder is the result of appending List to L1.

So, we want to append [-10,-5,6,7,8] to [9,2,3,4]. The list being appended to isn't empty, so we can skip that rule. By the second rule, the result has 9 as the first element, followed by the result of appending [-10,-5,6,7,8] to [2,3,4].

So, we want to append [-10,-5,6,7,8] to [2,3,4]. The list being appended to isn't empty, so we can skip that rule. By the second rule, the result has 2 as the first element, followed by the result of appending [-10,-5,6,7,8] to [3,4].

So, we want to append [-10,-5,6,7,8] to [3,4]. The list being appended to isn't empty, so we can skip that rule. By the second rule, the result has 3 as the first element, followed by the result of appending [-10,-5,6,7,8] to [4].

So, we want to append [-10,-5,6,7,8] to [4]. The list being appended to isn't empty, so we can skip that rule. By the second rule, the result has 9 as the first element, followed by the result of appending [-10,-5,6,7,8] to [].

So, we want to append [-10,-5,6,7,8] to []. The list being appended to is empty, so by the first rule, the result is [-10,-5,6,7,8].

Since the result of appending [-10,-5,6,7,8] to [] is [-10,-5,6,7,8], the result of appending [-10,-5,6,7,8] to [4] is [4,-10,-5,6,7,8].

Since the result of appending [-10,-5,6,7,8] to [4] is [4,-10,-5,6,7,8], the result of appending [-10,-5,6,7,8] to [3,4] is [3,4,-10,-5,6,7,8].

Since the result of appending [-10,-5,6,7,8] to [3,4] is [3,4,-10,-5,6,7,8], the result of appending [-10,-5,6,7,8] to [2,3,4] is [2,3,4,-10,-5,6,7,8].

Since the result of appending [-10,-5,6,7,8] to [2,3,4] is [2,3,4,-10,-5,6,7,8], the result of appending [-10,-5,6,7,8] to [9,2,3,4] is [9,2,3,4,-10,-5,6,7,8].

Epi

Thank you and @Mog , but i liked his "grapic" explanation more :) +1 – Digastric