Prolog Recursion with lists

Question

I am having a difficult time understand recursion in prolog. I can read examples and sometimes understand, but I mostly have a difficult time implementing them. For example, could someone code me how to find the summation all the elements in a list, and go through it? and tips on how to approach a question like this? Thanks!

Answer 1

A general "good" explanation is not possible, because a good explanation needs to link to the previous knoledgment of the person. I'm going, by example, assume you are able to made a "proof by induction".

Step1: Let start by the initial fact, "the sum of a set with a single element is the element itself". In prolog:

sum([A],A).

Step2: if the sum of a set Q is SQ, the sum of this set adding one element H is H+SQ. In prolog:

sum([H|Q],R) :- sum(Q,SQ), R is H+SQ.

thats all, you have the problem solved. But...

In general, we try to start by the most basic set, the empty one, so replace "step 1" that becames now: the sum of the elements of an empty set is 0:

sum([],0).

Finally, prolog is more efficiente if the rules are tail recursive (if the execution environment is not able to optimice by itself). That means a little change:

sum([],R,R).
sum([H|Q],SQ,R) :- T is SQ+H, sum(Q,T,R).

these rules can be understood as: Assume (assert) that sum of Q is SQ. In this case, sum of set Q plus an element H is SQ+H. The first one means, when there are no more elements in the pending set, the result is directly the acumulated sum.

Answer 2

Thinking recursively can be hard. See my answer to the question "Prolog programming - path way to a solution" for links to good resources on how to think recursively.

For instance, most recursive problems can be broken down into a few (1 or 2) special cases, and then, the general case. In your case — computing the sum of a list of numbers — one might look at it has having 1 or two special cases. First, you have to make a decision: What is the sum of an empty list? One might argue either that the sum of an empty list is zero, or that an empty list has no sum. Either is, arguable, a perfectly valid point-of-view.

In either event, the special cases are

• []. The empty list. The sum of the empty list is either 0, or nothing (in which case your predicate should fail.)

• [100]. A list of length one. The sum of a list of length 1 is obviously that value of the first and only entry.

And the more general case:

• [100,101,102]. The sum of a list of length greater than 1 can be computed by taking the value of the first item in the list and computing the sum of the remainder. Note that

  • The solution is defined in terms of itself, and
  • The problem is made smaller (by removing the 1st item from the list).

  Eventually, the problem will degenerate into one of the special cases, right?

Given all that, let us suppose that we've decided that the sum of the empty list is to be 0. That means our 2nd special case (a single element list) goes away, leaving us with a solution that can be described as

• The sum of an empty list is 0.
• The sum of a non-empty list is computed by
  • removing the 1st item from the list,
  • computing the sum of the remaining items,
  • adding the value of the 1st item to the sum of the remainder.

And since prolog is a declarative language, our solution is going to be pretty much identical to the description of the solution:

sum_of_list( []     , 0 ) .
sum_of_list( [N|Ns] , S ) :-
  sum_of_list(Ns,T) ,
  S is T+N
  .

The c