Comp210 Lab 4: list-of-bits review

Comp 210 Lab 4: list-of-bits review

From last week,

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 "meaning" of a list of bits 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)--namely 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)) ...))))

A function to convert a list of bits into a number (just following the data definition) is lob->num

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

Going the other direction--converting a number into a list of bits--doesn't have a template to follow. Last week we reasoned from the defined "meaning" of a list of bits to get: num->lob

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

Finally, the function zero? is built-in to Dr. Scheme; when working with bits it can be helpful to have the complementary function:

;; one?
;; takes in a bit,
;; returns #t/#f depending on whether a-bit is 1.
;; (only intended for bits!)
;;
(define one?
  (lambda (a-bit)
    (= 1 a-bit)))

Back to Lab 4
Back to Comp 210 Home