Prolog recursively append the list

Here's a code which recursively add the element X at the end of the list.

app(X, [], [X]).
app(X, [Y | S], [Y | S2]) :- app(X, S, S2).

Could anyone explain me how it works? Where's the return statement, what exactly the app(X, S, S2) [Y | S], [Y | S2] do?


  • You don't need return statement everything is done by unification (simply pattern matching). The clause:

    app(X, [Y | S], [Y | S2]) 

    states that the second argument is a list with head Y and tail S and the third argument is a list with head Y and tail S2. So it forces (by using unification) the heads of the two lists to be the same. Recursively the two lists become identical except the fact that the third argument list has one more element in the end (element X) and this is defined by the first clause. Note that second clause only works for lists with one or more elements. So as a base of the recursion when we examine the empty list (in the second parameter) then the third list due to first clause contains only one more element the element X.