Comp210 Lab 4: list-of-bit functions

Comp 210 Lab 4: list-of-bit functions

Table of Contents

Data definition

A bit is either

0, or

A list-of-bits is either

null, or

(cons b lob), where b is a bit, and lob is a list-of-bits.

The representation relationship is as follows:

null represents 0

(cons b l) represents b + 2 * [whatever-l-represents]. In other words, if lst is non-null, then lst represents (car lst) + 2 * [whatever-is-represented-by-(cdr-lst)]

(If you think about it, we are really defining a "value" function on list-of-bits, and the definition of the mathematical function is specified recursively, just like the data structure was.)

Program Template

We can do this much without even knowing what we are trying to write:

    (define lob-function
      (lambda (lob)
        (if (null? lob)
            ...
            ... (car lob) ... (lob-function (cdr lob)) ... )))

Since there are two possibilities for (car lob)--0 and 1--we may wish to add another test:

    (define fun-for-lob
      (lambda (lob)
        (if (null? lob)
            ...
            (if (zero? (car lob))
                ... (fun-for-lob (cdr lob)) ...
                ... (fun-for-lob (cdr lob)) ...))))

lob->num

    (define lob->num
      (lambda (lob)
        (if (null? lob)
            0
            (if (zero? (car lob))
                (* 2 (fun-for-lob (cdr lob)))
                (+ (* 2 (fun-for-lob (cdr lob))) 1)))))

num->lob

(define num->lob
  (lambda (n)
     (if (zero? n)
         null
         (cons (remainder n 2) (num->lob (quotient n 2))))))

Back to Lab 4
Back to Comp 210 Home