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

From: Bill Richter (richter at math.northwestern.edu)
Date: Thu May 6 22:50:22 EDT 2004

I'm learning define-struct from HtDP, to improve some "Lambda algebra"
code I wrote last year to cite in a Math paper.  

HtDP has nice examples of using define-struct to specify tree-like
data.  I liked 14.4 Extended Exercise: Evaluating Scheme.  Simple
Scheme expression are trees consisting of numbers & symbols connected
by + and * (both 2 children). The tree-connections are specified by:

(define-struct add (left right))
(define-struct mul (left right))

so (+ (* x x) (* y y)) is (make-add (make-mul 'x 'x) (make-mul 'y 'y))

My question (very specific below) is when should we use define-struct?
Any time we have a class of objects, say Widget, we can use
define-struct to specify lists of widgets, by 

(define-struct widgets (first rest))

Then we can define lists of widgets in this way

(define w (awidget lowidgets))

and then (widget-first w) and (widget-rest w) are the first & rest of
my list of widgets w.

So my general question is: is this considered to be useful?  Maybe
it's only useful if we have more complicated tree-like data.  HtDP
doesn't seem to pull out structures any times there's a listofWidget.

So here's my simple example that looks like lists of widgets.  I'm
working with a "tensor algebra over Z/2", and I have 1000 lines of
working but maybe-not-transparent DrScheme code.  I define

Monomial =lists of integers n >= 0

So (2 4 8) is a monomial.  The empty list is the "identity element."

I also define 
Polynomial = lists of monomials 

but actually, given any list of monomials, I replace it by the
polynomial given by quicksorting the list with left-lexicographical
order and then deleting repetitions.  (BTW Z/2 = deleting
repititions.)  The empty list is the important "zero element."

Then I have recursive functions : Polynomials ---> Polynomials.

I wrote the code where polynomials were lists of lists of integers.  I
tried to abstract the list-ness away with fancy names of functions:

(define (Poly+Poly X Y)
  ;; Returns the Lambda polynomial X + Y of two polynomials X & Y.
  (append X Y))

(define (Mono*Mono x y)
  ;; Returns the Lambda monomial x * y of two terms x & y.
  (append x y))

See, appending two lists of integers is multiplication, and appending
two lists of monomials is addition in the tensor algebra.  (BTW the
"lambda algebra" is a quotient of this tensor algebra.)

Anyway, I'm wondering if HtDP experts think there's any advantage to
using structures here to define Monomial & Polynomial.  I could say

(define-struct Mono (initial rest))
(define-struct Poly (first rest))

and then my definitions would become selectors:

(define (Mono-initial term)
  ;; Returns the initial  \i_1 of a nontrivial Lambda term \i_1 ... \i_n
  (first term))

(define (Mono-rest term) (rest term))

(define (Poly-first X) (first X))

(define (Poly-rest X) (rest X))

If this isn't the right list to post such a question to, I apologize,
and I can send it to the graveyard c.l.s.  But it seems to me that the
only folks who would be interested & experts are here.


Posted on the users mailing list.