Comparing Unknown Structs

Sometimes students are asked to write their own structure definitions instead of importing them from a module/teachpack. This can cause difficulties, as the testing code will not be able to see the student's definitions; as a result, none of the accessor methods will be available if required.

See also: SchemeModuleCreateStudentDefinedStruct.

Transformation to Vectors

Fortunately, scheme allows the transformation of arbitrary structures into vectors; the first entry in the vector is the name of the structure, and the remaining entries are the values stored in the structure in sequence. So, to get the values stored in a structure without the name, you just need a function similar to the following:

(define (cond-transform val)
 (if (struct? val)
     (vector-copy (struct->vector val) 1)
     val))

Example: Comparing Lines

The following example uses the idea of comparing two lines for equality. This is based off of the idea that students are asked to represent a line in two dimensions of the form Ax + By + C = 0 without being given a particular definition (for example, in a required module/teachpack) beyond the requirement that the fields A, B, C appear in that order.

The following code attempts to compare two line structs; in this scenario, the module would not be able to see the line definition, so it needs to convert these unknown structs into vectors in order to operate on them. It also requires the comparison of inexact values, as described at SchemeModuleCompareInexactValues.

#lang scheme/base
(provide line-equal?)

; If this is a struct, convert it to a vector;
; otherwise, leave it alone.
; NOTE: The returned vector has size one greater than the
; struct; the first field (#0) stores the name of the struct.
; This means this module could potentially check the type of
; struct it's passed in addition to the field values.
(define (cond-transform val)
  (if (struct? val)
      (struct->vector val)
      val))

; Reduce the line to lowest terms so it is more
; easily comparible to other lines.
(define (reduce a-line)
  (let ([a (vector-ref a-line 1)]
        [b (vector-ref a-line 2)]
        [c (vector-ref a-line 3)])
    (cond
      [(not (zero? c))
       (let ([ret (make-vector 4)])
         (vector-set! ret 1 (/ a c))
         (vector-set! ret 2 (/ b c))
         (vector-set! ret 3 1)
         ret)]
;       (make-line (/ a c) (/ b c) 1)]
      [(not (zero? b))
       (let ([ret (make-vector 4)])
         (vector-set! ret 1 (/ a b))
         (vector-set! ret 2 1)
         (vector-set! ret 3 0)
         ret)]
;       (make-line (/ a b) 1 0)]
      [(not (zero? a))
       (let ([ret (make-vector 4)])
         (vector-set! ret 1 1)
         (vector-set! ret 2 0)
         (vector-set! ret 3 0)
         ret)]
;       (make-line 1 0 0)]
      [else a-line])))

(define DEFAULT-%-DIFF 1)
(define EXPECTED-STRUCT-SIZE (+ 3 1))

(define (approximately-equal-helper expected result percent-diff)
  (and (number? expected) (number? result)
       (let* ((mult-factor (/ percent-diff 100))
              (expected-deviation (* expected mult-factor))
              (extreme-pt-1 (+ expected expected-deviation))
              (extreme-pt-2 (- expected expected-deviation))
              (max-acceptable (max extreme-pt-1 extreme-pt-2))
              (min-acceptable (min extreme-pt-1 extreme-pt-2)))
         (<= min-acceptable result max-acceptable))))
  
(define (line-equal? expected result)
  (let ([expected (cond-transform expected)] 
        [result (cond-transform result)] 
        [percent-diff DEFAULT-%-DIFF])
    (and (vector? expected) 
         (vector? result)
         (= (vector-length expected) EXPECTED-STRUCT-SIZE)
         (= (vector-length result) EXPECTED-STRUCT-SIZE)
         (let ([expected (reduce expected)]
               [result (reduce result)])
           (and (approximately-equal-helper (vector-ref expected 1)
                                            (vector-ref result 1)
                                            percent-diff)
                (approximately-equal-helper (vector-ref expected 2)
                                            (vector-ref result 2)
                                            percent-diff)
                (approximately-equal-helper (vector-ref expected 3)
                                            (vector-ref result 3)
                                            percent-diff))))))

#|
(define-struct line (A B C) #:transparent)
(line-equal? (make-line 2 3 4) (make-line 4 6 8)) ; => #t
(line-equal? (make-line 2 3 5) (make-line 4 6 8)) ; => #f
|#

Note that the approximately-equal-helper is only needed if the lines produce are expected to contain inexact values. Otherwise, the supplied values to all make-struct calls in the tests can be rationals, and these comparisons can be exact, meaning the three calls to approximately-equal-helper can be replaced with straightforward calls to equal? (with the percent-diff argument removed).

Topic revision: r2 - 2010-03-04 - TerryVaskor
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback