How to add polynoms in Prolog?

I have the following task:

Write a method that will add two polynoms. I.e 0+2*x^3 and 0+1*x^3+2*x^4 will give 0+3*x^3+2*x^4.

I also wrote the following code:

add_poly(+A1*x^B1+P1,+A2*x^B2+P2,+A3*x^B3+P3):-
    (
       B1=B2,
       B3 = B2,
       A3 is A1+A2,
       add_poly(P1,P2,P3)
    ;
       B1<B2,
       B3=B1,
       A3=A1,
       add_poly(P1,+A2*x^B2+P2,P3)
    ;
       B1>B2,
       B3=B2,
       A3=A2,
       add_poly(+A1*x^B1+P1,P2,P3)
    ).
add_poly(X+P1,Y+P2,Z+P3):-
    Z is X+Y,
    add_poly(P1,P2,P3).

My problem is that I don't know how to stop. I would like to stop when one the arguments is null and than to append the second argument to the third one. But how can I check that they are null? Thanks.

Solution

Several remarks:

Try to avoid disjunctions (;)/2 in the beginning. They need special indentation to be readable. And they make reading a single rule more complex — think of all the extra (=)/2 goals you have to write and keep track of.

Then, I am not sure what you can assume about your polynomials. Can you assume they are written in canonical form?

And for your program: Consider the head of your first rule:

add_poly(+A1*x^B1+P1,+A2*x^B2+P2,+A3*x^B3+P3):-

I will generalize away some of the arguments:

add_poly(+A1*x^B1+P1,_,_):-

and some of the subterms:

 add_poly(+_+_,_,_):-

This corresponds to:

add_poly(+(+(_),_),_,_) :-

Not sure you like this.

So this rule applies only to terms starting with a prefix + followed by an infix +. At least your sample data did not contain a prefix +.

Also, please remark that the +-operator is left associative. That means that 1+2+3+4 associates to the left:

?- write_canonical(1+2+3+4).
+(+(+(1,2),3),4)

So if you have a term 0+3*x^3+2*x^4 the first thing you "see" is _+2*x^4. The terms on the left are nested deeper.

For your actual question (how to stop) - you will have to test explicitly that the leftmost subterm is an integer, use integer/1 - or maybe a term (*)/2 (that depends on your assumptions).