;; The first three lines of this file were inserted by DrScheme. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-beginner-abbr-reader.ss" "lang")((modname t6-solns) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #8(#t constructor repeating-decimal #f #t none #f ())))
;;; CS 135 Fall 2007
;;; Tutorial 6: Recursion, Lists, and Tally Sets
;;; Sample Solutions
;; Data definition: natural number (nnum)
;; A natural number is either 0 or 1 plus a natural number.
;; The representation of the number 0
;(define zero 0)
;; Contract: my-zero?: nnum -> boolean
;(define (my-zero? n) (zero? n))
;; Contract: my-add1: nnum -> nnum
;(define (my-add1 n) (add1 n))
;; Contract: my-sub1: positive-nnum -> nnum
;(define (my-sub1 n) (sub1 n))
;;; I. Basic Arithmetic Functions
;; Contract: my+: tally tally -> tally
(define (my+ a b)
(cond [(my-zero? a) b]
[else (my+ (my-sub1 a) (my-add1 b))]))
;; Contract: my-: tally tally -> tally
(define (my- a b)
(cond [(my-zero? b) a]
[else (my- (my-sub1 a) (my-sub1 b))]))
;; Contract: my*: tally tally -> tally
;(define (my* a b)
; (cond [(my-zero? a) zero]
; [else (my+ b (my* (my-sub1 a) b))]))
;; Contract: my<: tally tally -> boolean
(define (my< a b)
(cond [(my-zero? b) false]
[(my-zero? a) true]
[else (my< (my-sub1 a)
(my-sub1 b))]))
;; Contract: my-quotient: tally tally -> tally
(define (my-quotient a b)
(cond [(my< a b) zero]
[else (my-add1 (my-quotient (my- a b) b))]))
;; Contract: my-remainder: tally tally -> tally
(define (my-remainder a b)
(my- a (my* (my-quotient a b) b)))
;;; II. Tally Sets
;; Data definition for tally
;; A tally represents a single natural number
;; A tally is a list of non-empty lists of 1's.
;; Every list of 1's except possibly for the last
;; has length 5. The last list of 1's has length no
;; greater than 5.
;;; A. Conversion
;; Contract: tally->num: tally -> nnum
;; Purpose: Convert from a tally set to a natural number
;; Examples: (tally->num (list (list 1 1 1 1 1) (list 1 1))) => 7
;; (tally->num empty) => 0
(define (tally->num alol)
(cond [(empty? alol) 0]
[else (+ (length (first alol))
(tally->num (rest alol)))]))
"Tests for tally->num"
(= 7 (tally->num (list (list 1 1 1 1 1) (list 1 1))))
(zero? (tally->num empty))
(= 5 (tally->num (list (list 1 1 1 1 1))))
;; Contract: list-of-1s: num -> list-of-nnums
;; Purpose: Creates a list of the given number of 1's
;; Examples: (list-of-1s 3) => (list 1 1 1)
(define (list-of-1s n)
(cond [(zero? n) empty]
[else (cons 1 (list-of-1s (sub1 n)))]))
"Tests for list-of-1s"
(equal? (list-of-1s 3) (list 1 1 1))
(empty? (list-of-1s 0))
;; Contract: num->tally: nnum -> tally
;; Purpose: Convert from a natural number to a tally set
;; Examples: (num->tally 4) => (list (list 1 1 1 1))
;; (num->tally 0) => empty
(define (num->tally n)
(cond [(zero? n) empty]
[(> n 5)
(cons (list 1 1 1 1 1)
(num->tally (- n 5)))]
[else (list (list-of-1s n))]))
"Tests for num->tally"
(equal? (num->tally 4)
(list (list 1 1 1 1)))
(empty? (num->tally 0))
(equal? (num->tally 8)
(list (list 1 1 1 1 1)
(list 1 1 1)))
;;; B. Arithmetic
;; A tally set representing 0
(define zero empty)
;; Contract: my-zero?: tally -> boolean
;; Purpose: Tell whether the given tally set represents 0.
;; Examples: (my-zero? empty) => true
;; (my-zero? (list (list 1 1 1))) => false
(define (my-zero? alol) (empty? alol))
"Tests for my-zero?"
(my-zero? empty)
(not (my-zero? (list (list 1 1 1))))
(not (my-zero? (list (list 1 1 1 1 1) (list 1 1 1 1 1))))
;; Contract: my-sub1: (nonempty tally) -> tally
;; Purpose: Subtract one line from the given nonempty tally set
;; Examples: (my-sub1 (list (list 1))) => empty
;; (my-sub1 (list (list 1 1 1 1 1) (list 1 1))) => (list (list 1 1 1 1 1) (list 1))
(define (my-sub1 alol)
(cond [(not (empty? (rest alol)))
(cons (first alol)
(my-sub1 (rest alol)))]
[(not (empty? (rest (first alol))))
(cons (rest (first alol))
(rest alol))]
[else empty]))
"Tests for my-sub1"
(empty? (my-sub1 (list (list 1))))
(equal? (my-sub1 (list (list 1 1 1 1 1) (list 1 1)))
(list (list 1 1 1 1 1) (list 1)))
;; Contract: my-add1: tally -> tally
;; Purpose: Add one line to the given tally set
;; Examples: (my-add1 empty) => (list (list 1))
;; (my-add1 (list (list 1 1 1 1 1) (list 1 1))) => (list (list 1 1 1 1 1) (list 1 1 1))
(define (my-add1 alol)
(cond [(empty? alol)
(list (list 1))]
[(= 5 (length (first alol)))
(cons (first alol)
(my-add1 (rest alol)))]
[else (cons (cons 1 (first alol))
(rest alol))]))
"Tests for my-add1"
(equal? (my-add1 empty) (list (list 1)))
(equal? (my-add1 (list (list 1 1 1 1 1) (list 1 1)))
(list (list 1 1 1 1 1) (list 1 1 1)))
;;; III. Slightly more complicated recursion
;;; A. Setting up the machinery
;; Contract: my-even? tally -> boolean
(define (my-even? alol)
(cond [(empty? alol) true]
[(empty? (rest alol))
(even? (length (first alol)))]
[else (my-odd? (rest alol))]))
;; Contract: my-odd: tally -> boolean
(define (my-odd? alol)
(cond [(empty? alol) false]
[(empty? (rest alol))
(odd? (length (first alol)))]
[else (my-even? (rest alol))]))
"Tests for my-even?"
(my-even? (num->tally 18))
(my-even? zero)
(not (my-even? (num->tally 5)))
"Tests for my-odd?"
(my-odd? (num->tally 11))
(my-odd? (list (list 1)))
(not (my-odd? (num->tally 34)))
;; Contract: double-group: list-of-nums -> list-of-nums
;; Purpose: Return a list with twice as many entries as the original one.
;; Example: (double-group (list 1 1 1)) -> (list 1 1 1 1 1 1)
(define (double-group alon)
(cond [(empty? alon) empty]
[else (cons (first alon)
(cons (first alon)
(double-group (rest alon))))]))
"Tests for double-group"
(equal? (double-group (list 1 1 1))
(list 1 1 1 1 1 1))
(empty? (double-group empty))
;; Contract: my-double: tally -> tally
;; Purpose: Produce a tally whose value is twice as large as the given
;; tally set
;; Examples: (my-double (num->tally 13)) => (num->tally 26)
;; (my-double zero) => zero
(define (my-double alol)
(cond [(empty? alol) empty]
[(= 5 (length (first alol)))
(cons (first alol)
(cons (first alol) (my-double (rest alol))))]
[(< (length (first alol)) 3)
(cons (double-group (first alol))
(my-double (rest alol)))]
[else
(list (list 1 1 1 1 1)
(rest (rest (rest (rest (rest (double-group (first alol))))))))]))
"Tests for my-double"
(= 26 (tally->num (my-double (num->tally 13))))
(= 6 (tally->num (my-double (num->tally 3))))
(my-zero? (my-double zero))
;; Contract: half-group: (even-length list-of-nums) -> list-of-nums
;; Purpose: Return a list with half as many entries as the original one.
;; Example: (half-group (list 1 1 1 1 1 1)) -> (list 1 1 1)
(define (half-group alon)
(cond [(empty? alon) empty]
[else (cons (first alon)
(half-group (rest (rest alon))))]))
"Tests for half-group"
(equal? (half-group (list 1 1 1 1 1 1))
(list 1 1 1))
(empty? (half-group empty))
;; Contract: my-half: tally -> tally
;; Purpose: Produce a tally whose value is half as large as the given
;; tally set
;; Examples: (my-half (num->tally 26)) => (num->tally 13)
;; (my-half zero) => zero
(define (my-half alol)
(cond [(empty? alol) empty]
[(empty? (rest alol))
(list (half-group (first alol)))]
[(empty? (rest (rest alol)))
(list (cons 1 (cons 1 (half-group (cons 1 (first (rest alol)))))))]
[else
(cons (first alol)
(my-half (rest (rest alol))))]))
"Tests for my-half"
(= 13 (tally->num (my-half (num->tally 26))))
(= 3 (tally->num (my-half (num->tally 6))))
(my-zero? (my-half zero))
;;; B. Faster multiplication
;; Contract: my*: tally -> tally
(define (my* a b)
(cond [(my-zero? a) zero]
[(my-even? a)
(my* (my-half a)
(my-double b))]
[else (my+ (my* (my-half (my-sub1 a))
(my-double b))
b)]))
;;; Tests for arithmetic functions
(define two (list (list 1 1)))
(define five (list (list 1 1 1 1 1)))
(define seven (list (list 1 1 1 1 1) (list 1 1)))
(define fourteen (list (list 1 1 1 1 1)
(list 1 1 1 1 1)
(list 1 1 1 1)))
"Tests for my+"
(equal? (my+ two five) seven)
(equal? (my+ fourteen zero) fourteen)
"Tests for my-"
(equal? (my- seven five) two)
(equal? (my- (my-add1 seven)
(my-add1 zero))
seven)
(my-zero? (my- fourteen fourteen))
"Tests for my*"
(equal? (my* seven two) fourteen)
(equal? (my* fourteen
(my-add1 zero))
fourteen)
(my-zero? (my* zero five))
"Tests for my<"
(my< two fourteen)
(not (my< seven five))
(not (my< five two))
(my< five seven)
"Tests for my-quotient"
(equal? (my-quotient fourteen two)
seven)
(equal? (my-quotient fourteen five)
two)
(my-zero? (my-quotient five seven))
"Tests for my-remainder"
(equal? (my-remainder seven five) two)
(my-zero? (my-remainder fourteen seven))