[plt-scheme] when to use define-struct?

From: Bill Richter (richter at math.northwestern.edu)
Date: Fri May 7 19:53:08 EDT 2004

   I don't think a monomial is actually a list of numbers but rather
   you have chosen to represent a monomial in such a way.  

     (define-struct monomial coefficient)

Thanks, Noel.  I think I wasn't at all clear, so let me try again.
Folks are more familiar with integer polynomials in x, y, & z, e.g.

x y z + 6 y^2 + 10 x^5 

By "Z/2 tensor algebra", I meant the variables x, y, & z don't commute
(i.e. x y != y x), and the coefficients are all 0 or 1 (not 6 or 10).
But these are probably not important distinctions here.

Question: do structs help with integer polynomials?  A polynomial is a
sum of monomials, with integer coefficients, and a monomial is a
product of variables.  As to variables, instead of x, y, z, why not
say x_0, x_1, x_2 (or in my case, \0, \1, \2.)  A product of the
variables x_0, x_1, x_2,... is just a list of the indices: x_6 x_5 x_9
is represented as the list (6 5 9).  That's what I meant by

Monomial =lists of integers n >= 0

And a polynomial is a list of lists multiplied by integer
coefficients.  I'd translate the above example as:

x_0 x_1 x_2 + 6 x_1 x_1  + 10 x_0 x_0 x_0 x_0 x_0 

represented as ((0 1 2) 6*(1 1) 10*(0 0 0 0 0)).  

So what's a good data abstraction for integer polynomials?  There's
all kinds of manipulations we have to make with the polynomials: we
have to simplify them, sort them, they're commutative in addition and
multiplication (not for me), and we have to handle the coefficients
(not for me, since the nonzero ones all have coeffiecient 1).  

Maybe folks here have thought about this.  You seemed to like
polynomials as just lists of monomials.  Then we can use the DrScheme
quicksort & mergesort on polynomials.  In that case, maybe I'd say

(define-struct monomial (coefficient first rest))

so 6 y^2 z = 6 x_1 x_1 x_2 = (make-monomial 6 1 '(1 2))

and Polynomial = list of Monomial.


Posted on the users mailing list.