Scheme Programming/Abstractions with Data

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Introduction to Complex Numbers

In order to show how abstractions with data can be built, we're going to go through making a complex number package. A complex number is one that has 2 parts, a real part, and an imaginary part. They are often written in one of two ways, in rectangular form:

And in polar form:

Now, we can can do all of the usual arithmetic with complex numbers, addition, subtraction, multiplication and division. There are simple formulae for this;

Addition:

Subtraction:

Multiplication:

Division:

Note how multiplication and division are best expressed in polar form, while addition and subtraction are best expressed in rectangular form. This raises an interesting question: How does one best go about computing these? Do we have one internal representation? If so, which do we choose? There are a large amount of questions. These can be answered by trying to implement a new type of data: the complex number type.

Creating our Generic 'Typed' Variable

Firstly, we shall create a generic 'Typed' variable:

(define typed-variable
  (lambda (type value)
    (cons 'Typed (list type value))
  )
)

We now need a way to tell if a given variable has a type:

(define typed?
  (lambda (var)
    (and (list? var) (= 'Typed (car var)))
  )
)

Now, we've introduced two important concepts here, a 'Predicate' and a 'Constructor'. The first is a construct to find if some data is of the correct form, and the second is a procedure that builds our data structure for us.

We must have a way of extracting our data (in this case, the type) from this structure, a way of 'selecting' it:

(define type-of
  (lambda (var)
    (if (typed? var)
      (car (cdr var)
    )
  )
)

Creating our Complex Number Data Type

Building our Constructors

Using this typed value, we can go on to form a more detailed data structure for out complex number:

(define complex-rect
  (lambda (a b)
    (typed-variable 'Rect-Complex (list a b))
  )
)

Now let's continue, and create a complex-polar:

(define complex-polar
  (lambda (r thet)
    (typed-variable 'Polar-Complex (list r thet))
  )
)
(define complex
  (lambda (type first-var second-var)
    (if (equal? 'type Polar)
        (cons (complex-polar first-var second-var) 
              (complex-rect (sqrt (+ (expt first-var 2) 
                                     (expt second-var 2)
                                  )
                            ) 
                            0
              )
        )  ;; Change second half to be the calculated values.
        (cons (complex-polar 0 0) (complex-rect first-var second-var))
    )
  )
)

Building our Predicates

We have our constructors, now we need our predicates:

(define is-complex?
  (lambda (var)
    (and (typed? (car var)) 
         (or (= 'Rect-Complex (type-of (car var))) 
             (= 'Polar-Complex (type-of (car var)))
         )
    )
  )
)


Now we can define our arithmetic in terms of these procedures.