MHB Polynomial Arithmetic in Lisp: How to Begin?

[Nono713]

Ok, that makes sense and I've changed it now to represent the new way. I'm having a bit of an issue with some Lisp syntax for the base case. I know the logic behind what I want to do. I think the best way is to say when the remainder, the variable that holds everything after the first two polynomials is empty, return the polynomial.

In code:

    (if(eq nil remainder)
       (p1))

I get a warning saying that P1 is an undefined function. This is probably a stupid question but I just can't seem to get it working.

Actually that's not quite right (your logic). If the remainder is nil, there could still be 2 elements in the list, so they should still be collected. What you need to check for is when there are less than 2 elements, and that happens if (and only if) the second element is nil. So this is the element you should check against for the base case. (you're getting there!)

As for your second question, I used the "null" function to check for nil:

(if (null yourvar)
    ; ...
)

 

[JamesBwoii]

Actually that's not quite right (your logic). If the remainder is nil, there could still be 2 elements in the list, so they should still be collected. What you need to check for is when there are less than 2 elements, and that happens if (and only if) the second element is nil. So this is the element you should check against for the base case. (you're getting there!)

As for your second question, I used the "null" function to check for nil:

(if (null yourvar)
    ; ...
)

Of course, obvious now you've said it! I've created a new variable that holds the second element of the list:

       (second-element(car(cdr p1))))

and then this is my base case:

    (if(null second-element )
       p1)

Not sure if it's working though, when running it I still end up with NIL being the last thing printed to the console.

 

[Nono713]

Of course, obvious now you've said it! I've created a new variable that holds the second element of the list:

       (second-element(car(cdr p1))))

and then this is my base case:

    (if(null second-element )
       p1)

Not sure if it's working though, when running it I still end up with NIL being the last thing printed to the console.

Well, there's two things I can think of. One, are you actually printing the result of the function? Like this at the end:

(print(poly ...))

Also, perhaps the "p1" here in your code doesn't act as a "return" like in imperative languages. I must confess my Lisp is not good enough to answer that question, but in my implementation I used an if/else so that if the second element is not null, then the function continues with the logic and checks if the two elements are equal and so on... you could try this (to be honest it seems it should work that way, as a functional language)

 

[JamesBwoii]

I couldn't seem to get the 'if else' code working in Lisp so I just left it as two separate ifs. I think it's working as it should now.

Here's the code:

(defun poly (p1)
  (let((e1(car(car(cdr(car p1))))) (e2(car(car(cdr(car(cdr p1))))))
       (x1(car(cdr(car(cdr(car p1)))))) (x2(car(cdr(car(cdr(car(cdr p1)))))))
       (c1(car(car p1))) (c2(car(car(cdr p1))))
       (remainder(cdr(cdr p1)))
       (second-element (car(cdr p1))))
    
    (if(null second-element)
      (format t "~a~%" p1)

    (if(and(equal x1 x2)(equal e1 e2))
      (poly(append (list(list(+ c1 c2)(list e1 x1))) remainder))
      (format t "~a~%" p1)))))

Given input:

(poly '((5(2 x))(3(2 x))(10(2 x))(15(2 x))(20(2 x))))

Output is:

((53 (2 X)))
NIL

And input with a Y variable on the end.

(poly '((5(2 x))(3(2 x))(10(2 x))(15(2 x))(20(2 y))))

gives

((33 (2 X)) (20 (2 Y)))
NIL

 

[Nono713]

Looks fine to me, if a bit messy (I would personally first find the first two elements using "let", and then inside that let use these elements to access the variable and exponents for both of them, instead of starting from scratch from p1 every time).

So what's next now, say to get addition done? You need exactly one thing: a function to sort the list based on the variable + exponent, this will require you to read up on Lisp's sorting function. Call this function "sortpoly". Then, addition can be implemented as:

(defun addpoly (p1 p2)
    (collect-terms(sortpoly(append p1 p2)))
)

Here collect-terms is the function you call "poly", which we have been working on so far. Do you understand why addition can be implemented in this way? If so, implement sortpoly and addpoly.

As a bonus, you might notice that if you use your "addpoly" function on, say, ((1(2 x)) and ((-1(2 x)) you will get ((0(2 x)). This is not technically wrong, but zero times anything is still zero, so see if you can implement a function to remove terms with a zero coefficient from a polynomial. You can use a recursive function in the same spirit as "poly"/"collect-terms" (by taking a look at the first element of the polynomial, checking if its constant is zero or not, discarding it if appropriate, and recursing on the rest of the polynomial).

 

[JamesBwoii]

Looks fine to me, if a bit messy (I would personally first find the first two elements using "let", and then inside that let use these elements to access the variable and exponents for both of them, instead of starting from scratch from p1 every time).

So what's next now, say to get addition done? You need exactly one thing: a function to sort the list based on the variable + exponent, this will require you to read up on Lisp's sorting function. Call this function "sortpoly". Then, addition can be implemented as:

(defun addpoly (p1 p2)
    (collect-terms(sortpoly(append p1 p2)))
)

Here collect-terms is the function you call "poly", which we have been working on so far. Do you understand why addition can be implemented in this way? If so, implement sortpoly and addpoly.

As a bonus, you might notice that if you use your "addpoly" function on, say, ((1(2 x)) and ((-1(2 x)) you will get ((0(2 x)). This is not technically wrong, but zero times anything is still zero, so see if you can implement a function to remove terms with a zero coefficient from a polynomial. You can use a recursive function in the same spirit as "poly"/"collect-terms" (by taking a look at the first element of the polynomial, checking if its constant is zero or not, discarding it if appropriate, and recursing on the rest of the polynomial).

When you say sort by the variable and exponent you mean sort alphabetically for the variable and say sort from low to high for the exponent?

I assume sorting by the variable is the priority so the whole list would be ordered alphabetically by variable then each group of the same variables would be ordered by exponent.

Then if two polynomials were being added together and had the same variable and exponent they could be added.

 

[Nono713]

When you say sort by the variable and exponent you mean sort alphabetically for the variable and say sort from low to high for the exponent?

I assume sorting by the variable is the priority so the whole list would be ordered alphabetically by variable then each group of the same variables would be ordered by exponent.

Then if two polynomials were being added together and had the same variable and exponent they could be added.

You just need all terms with the same variable AND exponent (remember - you can't add $x$ to $x^2$) to appear next to one another in the list after sorting it. So basically any consistent sorting criteria will do the job. As such, you can simply tell Lisp to sort the list based on the (variable exponent) part of the elements. You can't just call sort directly, because that'll sort the list based on (constant (variable exponent)) which isn't what you want. Check out the built-in sort function, it does let you specify how to carry out the sort; specifically, look at the key parameter.

Also, helpful tip when writing Lisp code: indent it. That tends to make it much easier to follow your own code, especially when writing complex expressions.

 

[Nono713]

For what it's worth (you've already completed this function, so there's no harm in showing a different approach) this was my implementation of your "poly" function. It's similar to yours, except different naming and two "let" sections:

(defun collect (l)
    (let ((m1(car l))
          (m2(car(cdr l)))
          (rem(cdr(cdr l))))

        (if (null m2)                                                          ; If the list has less than 2 elements
      	    l                                                                  ; then return the list (nothing to collect)
            (let ((c1(car m1))                                                 ; else, extract (c1, t1), (c2, t2) from m1 and m2
                  (c2(car m2))
                  (t1(car(cdr m1)))
                  (t2(car(cdr m2))))

                (if (equal t1 t2)                                              ; if t1 == t2
                    (collect (append (list (list (+ c1 c2) t1)) rem))          ; then return collect((c1 + c2, t1) + rem)
                    (append (list m1) (collect (append (list m2) rem)))        ; else return (c1, t1) + collect((c2, t2) + rem)
                )
            )
        )
    )
)

Notice that the function is not even aware that the terms (here t1 and t2) contain variables and exponents. It just doesn't care, all it assumes is that they can be compared when it calls "equal" ("equal" on two lists compares the lists element-wise). This is what you are aiming for in a functional implementation, you want the least specific, most general function that will operate on as wide a range of types as possible.