How to perform arithmetic on elements of a Prolog list

Question

Background

A list of integer coefficients can be used to represent a polynomial (in X). For example, 1 + 3x + 3x^2 + 2x^3 is represented by [1,3,3,2].

Let P be one of these lists.

I need to write axioms that take these coefficients and do different things with them.

Example: axioms for a relation eval(P,A,R) where R is the result of evaluating the polynomial represented by P at X = A (expect P and A to be fully instantiated). For example, eval([3,1,2],3,R) produces R=24. (This is because 3(3)^0 + 1(3)^1 + 2(3)^2 = 3 + 3 + 18 = 24).

This Prolog tutorial discusses searching a list recursively: "It sees if something is the first item in the list. If it is, we succeed. If it is not, then we throw away the first item in the list and look at the rest".

on(Item,[Item|Rest]).  

on(Item,[DisregardHead|Tail]):-

      on(Item,Tail).

Question

How does this code throw away the first item in the list?

The question then becomes, once I've found it, how do I use it to calculate as described above?

Answer 1

How does this code throw away the first item in the list?

By calling on recursivelly on the list's tail, you're ignoring the first element. And since you won't use it, you should call it _ instead of DisregardHead (some compilers will warn you of "singleton variable").

once I've found it, how do I use it to calculate as described above?

Well, on is supposed to return multiple results - one for each match - while your goal is to have a single result that takes the whole list into account. So you shouldn't disregard the first element, but incorporate it in the results. Example:

my_pred([],0).
my_pred([Item|Tail],Result) :-
    my_pred(Tail,IntermResult),
    combine(Item,IntermResult,Result). % Ex.: Result is Item + IntermResult

I haven't given a complete code since it appears you're still learning, but can do if that's what you want. This is also a very simple example, and not optimized (i.e. no tail recursion).

Additional hint: if you express your polinomial this way, it should become clear how a recursive calculation could be done:

1 + x * (3 + x * (3 + x * (2 + x * 0)))

Answer 2

I made a 90 sec video to show how you can use SWI-Prolog's guitracer to intuitively understand simple Prolog programs. On Ubuntu/Debian just do sudo apt-get install swi-prolog and you can try out the debugger yourself using the commands in the video (which are swipl, [filename] (load file), guitracer., trace. and then the query).

Right click the image and choose "View Image" (Firefox) if the text is unreadable.