6 Replies - 1761 Views - Last Post: 06 February 2013 - 01:19 PM

#1 NecroWinter  Icon User is offline

  • D.I.C Regular

Reputation: 35
  • View blog
  • Posts: 318
  • Joined: 21-October 11

CLisp: Using mapcar for polynomial multiplication

Posted 05 February 2013 - 08:43 PM

(common lisp, sorry I forgot to put it in the title, cant edit it as far as I know)
Generally speaking, I know how to use mapcar, but this particular situation has me stumped.

Assume that we have two terms, and two lists (each list has two terms)

you know how if you were to multiply a polynomial, you take the first term in the first list, and distribute it across every item in the second list, then goto the second item in the first list and multiply it to everything in the second list etc?

How would you do that in lisp?


I am using a structure that looks like:
(defstruct term coef exp)



the code:
(defun poly-mul (p q)

(labels (
	 (mlt (t1 t2)
	   (make-term 
	    :coef (* (term-coef t1)(term-coef t2))
	    :exp  (+ (term-exp t1)(term-exp t2))))
	    
	    (pml (t3 t4)
	    (if (null t3) nil
	    (cons (mapcar #'mlt  (list (car t3)) t4) (pml (cdr t3) t4))))
	    
	    
	    
	    )
(pml p q)

 ))




input: (poly-mul (list (make-term :coef 1 :exp 3) (make-term :coef 2 :exp 2))(list (make-term :coef 1 :exp 4) (make-term :coef 2 :exp 3)))

-
output: ((#S(TERM :COEF 1 :EXP 7)) (#S(TERM :COEF 2 :EXP 6)))

the input in more readable terms is: p:(1^3,2^2) q:(1^4, 2^3)

what I expect is something like 1^7, 2^6, 2^6, 4^5 or (1^7, 2^6) (2^6, 4^5)
(I intentionally omitted #S(term :coef :exp) etc)

im not sure why my code doesnt goto the next term in the first list properly, hopefully someone can help

This post has been edited by NecroWinter: 05 February 2013 - 10:54 PM


Is This A Good Question/Topic? 0
  • +

Replies To: CLisp: Using mapcar for polynomial multiplication

#2 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2091
  • View blog
  • Posts: 3,185
  • Joined: 21-June 11

Re: CLisp: Using mapcar for polynomial multiplication

Posted 06 February 2013 - 02:53 AM

I think you think that (mapcar action list1 list2) applies the given action to each element in list1 and each element list2 Cartesian product-style, i.e. like a nested loop. But that's not how it works. What it does is it iterates both lists in parallel, i.e. it applies the action to the first element of list1 and the first element of list2, then to the second element of list1 and the second element of list2 and so on - never to elements that aren't at the same index. So since the first list you pass to mapcar only ever has one element, it will also only use the first element of the second list.

To combine each element (car t3) with each element from t4, you should call mapcar with only one list as argument (t4). The function given to mapcar should then call mlt with (car t3) and the given element of t4 as arguments. For that the function needs to have access to t3, so it either needs to be a local function inside pml or a lambda.

Instead of using mapcar inside a recursive function, it would be even better to use two nested calls to mapcar (i.e. one that iterates over every element in t3 and one that iterates over every element in t4) and no recursion at all.
Was This Post Helpful? 2
  • +
  • -

#3 NecroWinter  Icon User is offline

  • D.I.C Regular

Reputation: 35
  • View blog
  • Posts: 318
  • Joined: 21-October 11

Re: CLisp: Using mapcar for polynomial multiplication

Posted 06 February 2013 - 10:25 AM

I feel like im close, any idea why I get the following error?

[17]> (poly-mul (list (make-term :coef 1 :exp 5)(make-term :coef 4 :exp 2))(list (make-term :coef 2 :exp 3)(make-term :coef 8 :exp 1)))

*** - CAR: #S(TERM :COEF 2 :EXP 3) is not a list



(defun poly-mul (p q)

(mapcar (lambda (x)
	  (mapcar (lambda (y) (make-term 
			       :coef (*(term-coef (car y))
				       (term-coef (car x)))
			       :exp (+ (term-exp (car x))
				       (term-exp (car y))))) q)) p)


)



Was This Post Helpful? 0
  • +
  • -

#4 NecroWinter  Icon User is offline

  • D.I.C Regular

Reputation: 35
  • View blog
  • Posts: 318
  • Joined: 21-October 11

Re: CLisp: Using mapcar for polynomial multiplication

Posted 06 February 2013 - 10:31 AM

I just tried the following, and got incorrect results
input: (poly-mul (list (make-term :coef 1 :exp 5)(make-term :coef 2 :exp 1))(list (make-term :coef 1 :exp 3)(make-term :coef 4 :exp 1))
)

out:((#S(TERM :COEF 1 :EXP 8) #S(TERM :COEF 4 :EXP 6))
(#S(TERM :COEF 2 :EXP 4) #S(TERM :COEF 8 :EXP 2)))



(defun poly-mul (p q)

(mapcar (lambda (x)
	  (mapcar (lambda (y) (make-term 
			       :coef (*(term-coef  y)
				       (term-coef  x))
			       :exp (+ (term-exp  x)
				       (term-exp  y)))) q)) p)


)

This post has been edited by NecroWinter: 06 February 2013 - 10:31 AM

Was This Post Helpful? 0
  • +
  • -

#5 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2091
  • View blog
  • Posts: 3,185
  • Joined: 21-June 11

Re: CLisp: Using mapcar for polynomial multiplication

Posted 06 February 2013 - 10:52 AM

View PostNecroWinter, on 06 February 2013 - 06:25 PM, said:

(mapcar (lambda (x)
	  (mapcar (lambda (y) (make-term 
			       :coef (*(term-coef (car y))
				       (term-coef (car x)))
			       :exp (+ (term-exp (car x))
				       (term-exp (car y))))) q)) p)



x and y are elements of the lists - they aren't lists themselves. So you can't use car on them. Just use them directly.

View PostNecroWinter, on 06 February 2013 - 06:31 PM, said:

I just tried the following, and got incorrect results
input: (poly-mul (list (make-term :coef 1 :exp 5)(make-term :coef 2 :exp 1))(list (make-term :coef 1 :exp 3)(make-term :coef 4 :exp 1))
)

out:((#S(TERM :COEF 1 :EXP 8) #S(TERM :COEF 4 :EXP 6))
(#S(TERM :COEF 2 :EXP 4) #S(TERM :COEF 8 :EXP 2)))


Why is that an incorrect result? Looks correct to me: (x5 + 2x) * (x3 + 4x) = x8 + 4x6 + 2x4 + 8x2.
Was This Post Helpful? 1
  • +
  • -

#6 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2091
  • View blog
  • Posts: 3,185
  • Joined: 21-June 11

Re: CLisp: Using mapcar for polynomial multiplication

Posted 06 February 2013 - 11:03 AM

If you want the result to be a flat list rather than a nested list, you can replace the outer mapcar with mapcan. mapcan is like mapcar, except that it takes the results of the function application (which must be lists) and concatenates them together into one flat list.
Was This Post Helpful? 1
  • +
  • -

#7 NecroWinter  Icon User is offline

  • D.I.C Regular

Reputation: 35
  • View blog
  • Posts: 318
  • Joined: 21-October 11

Re: CLisp: Using mapcar for polynomial multiplication

Posted 06 February 2013 - 01:19 PM

My mistake, I thought I was putting something else in for the input, The results WERE correct, thank you
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1