recursion in prolog (on lists)

Question

can someone please help me just w/ the basics on performing recursive prolog functions..

append([],X,X). % base
append([X|Y],Z,[X|W]) :- append(Y,Z,W). %recursive

% base case
addup([], 0). % sum of the empty list of numbers is zero

% recursive case: if the base-case rule does not match, this one must:
addup([FirstNumber | RestOfList], Total) :-
    addup(RestOfList, TotalOfRest),   % add up the numbers in RestOfList
    Total is FirstNumber + TotalOfRest.

Can someone explain either in English or in C/C++/Java whatever.. how the steps. I actually would prefer to see something like append or reverse.. I'm mostly just manipulating lists of variables instead of integers.. (I've tried to work through append like 10 times.. ugh).

Solution 1

The free online book "Learn Prolog Now" has a section dedicated to explaining the steps that append performs:

http://cs.union.edu/~striegnk/learn-prolog-now/html/node47.html#subsec.l6.defining.append

Solution 2

append(A, B, R) means that R is the result of appending A to B.

The base case

append([], X, X).

says that if A = [] and B = X then R = X = B: an empty list A appended to some other list B is equal to B.

The recursive case

append([X | Y], Z, [X | W]) :- append(Y, Z, W).

says that if A = [X | Y] is a non-empty list to append to B = Z, and if W is Y appended to Z, then R = [X | W].

Another way of saying it is: to append a non-empty list A to another list B, first append the tail of A to B and then add the head of A to the front of the list.

Comments

[DJPlayer]

this follows the best format IMO. I've seen numerous ones like this just not translated to english for recursion. is the recursive version always read from left to right.. aka ", = and" thus operation perform in order left to right.. ([x|y], z, [x|w]). but only if append(y,z,w) holds.

[DJPlayer]

this is the best step by step answer I've seen.. and I've looked through several books. Makes far more sense now after looking at a trace