(define (length vals)
   (if (null? vals)
       0
       (+ 1 (length (cdr vals)))))

(define (length vals)
   (define (unsafe-length vals) ...)
   (if (list? vals)
       (unsafe-length vals)
       (error "bad input" length vals)))

(length '(6 9 3))
(+ 1 (length '(9 3)))
(+ 1 (+ 1 (length '(3))))
(+ 1 (+ 1 (+ 1 (length '()))))
(+ 1 (+ 1 (+ 1 0)))
(+ 1 (+ 1 1))
(+ 1 2)
3

|(length vals)| = O(n)
[(length vals)] = O(n)

(define (length vals)
   (if (not (list? vals))
       (error "bad input" length vals)
       (do ((count 0 (+ 1 count))
              (tail vals (cdr tail)))
           ((null? tail) count))))

|(length vals)| = O(n)
[(length vals)] = O(1)

LIST ::= () | (VALUE . LIST)

(define (list? val)
   (cond ((null? val) #t)
      ((pair? val) (list? (cdr val)))
      (else #f)))

|(list? val)| = O(n)
[(list? val)] = O(1).

(define fail 'fail)

(define (get prop alist)
   (let ((association (assoc prop alist)))
      (and association (cdr association)))) ;?!

(define (get prop alist)

   (define (unsafe-get prop alist) ???)

   (if (alist? alist)
       (unsafe-get prop alist)
       (error "bad input" get alist)))

(define (unsafe-get prop alist)
   (cond ((null? alist) fail)
      ((equal? prop (caar alist)) (cdar alist))
      (else (unsafe-get prop (cdr alist)))))

(get 3 '((1 . a) (2 . b) (3 . c)))
(unsafe-get 3 '((1 . a) (2 . b) (3 . c)))
(unsafe-get 3 '((2 . b) (3 . c)))
(unsafe-get 3 '((3 . c)))
3

|(unsafe-get prop alist)| = O(n)
[(unsafe-get prop alist)] = O(1)

(define (rem prop alist)
   (if (alist? alist)
      (cons (cons prop fail) alist)
      (error "bad input" rem alist)))

(define (rem prop alist)

   (define (unsafe-rem prop alist) ???)

   (if (alist? alist)
      (unsafe-rem prop alist)
      (error "bad input" rem alist)))

(define (unsafe-rem prop alist)
   (cond ((null? alist) alist)
      ((equal? prop (caar alist)) (cdr alist))
      (else (unsafe-rem prop (cdr alist)))))

(rem 2 '((1 . a) (2 . b) (3 . c)))
(unsafe-rem 2 '((1 . a) (2 . b) (3 . c)))
(unsafe-rem 2 '((2 . b) (3 . c)))
((3 . c))

(define (unsafe-rem prop alist)
   (cond ((null? alist) alist)
      ((equal? prop (caar alist)) (cdr alist))
      (else (cons (car alist) (unsafe-rem prop (cdr alist))))))

(rem 2 '((1 . a) (2 . b) (2 . b)))
(unsafe-rem 2 '((1 . a) (2 . b) (2 . b)))
(cons '(1 . a) (unsafe-rem 2 '((2 . b) (2 . b))))
(cons '(1 . a) '((2 . b)))
((1 . a) (2 . b))

(define (unsafe-rem prop alist)
   (cond ((null? alist) alist)
      ((equal? prop (caar alist))
         (unsafe-rem prop (cdr alist)))
      (else (cons (car alist) (unsafe-rem prop (cdr alist))))))

(rem 4 '((1 . a) (2 . b) (3 . c)))
(unsafe-rem 4 '((1 . a) (2 . b) (3 . c)))
(cons '(1 . a) (unsafe-rem 4 '((2 . b) (3 . c))))
(cons '(1 . a)
   (cons '(2 . b) (unsafe-rem 4 '((3 . c)))))
(cons '(1 . a) (cons '(2 . b) (cons '(3 . c) '())))
(cons '(1 . a) (cons '(2 . b) '((3 . c))))
(cons '(1 . a) ' ((2 . b) (3 . c)))
((1 . a) (2 . b) (3 . c))

|(unsafe-rem prop alist)| = O(n)
[(unsafe-rem prop alist)] = O(n)

(define (rem prop alist)
   (if (not (alist? alist))
       (error "bad input" rem alist)
       (do ((tail alist (cdr tail))
         (result (if (equal? prop (caar tail))
               result
               (cons (car tail) result))))
          ((null? tail) (reverse result)))))

(define (put prop val alist)
   (define assoc (cons prop val))
   (if (alist? alist)
       (cons assoc (rem prop alist))
       (error "bad input" put alist)))

(define (make-alist props vals)
   (if (and (list? props)
      (list? vals)
      (= (length props) (length vals)))
       (map cons props vals)
       (error "bad input(s)" make-alist props vals)))

(define (alist? val)
   (cond ((null? val) #t)
      ((pair? val)
         (and (pair? (car val))
            (alist? (cdr val))))
      (else #f)))

(define (noise? msg) ...)

(define (filter noise? msgs)

   (define (unsafe-filter noise? msgs) ???)

   (if (and (procedure? noise?) (list? msgs))
       (unsafe-filter noise? msgs)
       (error "bad input(s)" filter noise? msgs)))

> (filter odd? '(1 2 3 4 5 6 7 8 9))
(2 4 6 8)
> (filter prime? '(1 2 3 4 5 6 7 8 9))
(1 4 6 8 9)

(define (unsafe-filter noise? msgs)
   (cond
      ((null? msgs) '())
      ((noise? (car msgs))
         (unsafe-filter noise? (cdr msgs)))
      (else
         (cons (car msgs)
            (unsafe-filter noise? (cdr msgs))))))

|(filter pred? msgs)| = O(n)
[(filter pred? msgs)] = O(n)

(define (filter noise? msgs)
   (if (or (not (procedure? noise?))
      (not (list? msgs)))
       (error "bad input(s)" filter noise? msgs)
       (do
         ((tail msgs (cdr tail))
          (result
            '()
            (if (noise? (car tail))
               result
               (cons (car tail) result))))
          ((null? tail) (reverse result)))))

(define (amp msg) ...)

(define (unary-map amp msgs)

   (define (unsafe-map amp msgs) ???)

   (if (and (procedure? amp) (list? msgs))
       (unsafe-map amp msgs)
       (error "bad input(s)" unary-map amp msgs)))

(define (unsafe-map amp msgs)
   (if (null? msgs)
       '()
       (cons (amp (car msgs))
             (unsafe-map amp (cdr msgs))))))

(define (unary-map amp msgs)
   (if (or (not (procedure? amp)) (not (list? msgs)))
       (error "bad input(s)" unary-map amp msgs)
       (do ((tail msgs (cdr tail))
         (result '() (cons (amp (car tail)) result)))
         ((null? tail) (reverse result)))))

(define (map m-amp . m-msgs)

   (define (unsafe-map m-msgs) ???)

   (if (and (procedure? amp) (all? list? m-msgs))
       (unsafe-map m-amp m-msgs)
       (error "bad input(s)" map m-amp m-msgs)))

(define (unsafe-map m-msgs)
   (if (some? null? m-msgs)
       '()
       (let ((first (apply m-amp (unary-map car m-msgs))))
         (cons first (unsafe-map (unary-map cdr m-msgs))))))

(define (combiner first rest) ...)

(define (accum combiner init vals)

   (define (unsafe-accum combiner init vals) ???)

   (if (and (procedure? combiner) (list? vals))
       (unsafe-accum combiner init vals)
       (error "bad input(s)" accum combiner vals)))

(define (unsafe-accum combiner init msgs)
   (if (null? msgs)
       init
       (combiner
         (car (msgs))
         (unsafe-accum combiner init (cdr msgs)))))

(define (accum combiner init msgs)
   (if (or (not (procedure? combiner))
          (not (list? msgs)))
       (error "bad inputs to accum: " combiner msgs)
       (do ((tail msgs (cdr tail))
            (result init (combiner (car tail) result)))
          ((null? tail) result))))

(define (avg . scores)
   (/ (accum + 0 scores) (length scores)))

(define (m-to-n m n)

   (define step 1)     decrement amount
   (define scale 1)     scaling factor

   (if (not (and (real? m) (real? n)))
       (error "bad input(s)" m-to-n m n)
       (do ((i n (- i step))
             (msgs '() (cons (* scale i) msgs)))
           ((< i m) msgs))))

(define (sum-odd-squares n)
   (accum + 0
      (map square
         (filter even?
            (m-to-n 1 n)))))

(define (length vals)
   (define (combiner m n) (+ n 1)) ; ignores m!
   (accum combiner 0 vals))

(define (rem prop alist)
   (define (noise? association)
      (equal? prop (car association)))
   (filter noise? alist))

TREE ::= () | LEAF | PARENT

PARENT ::= (TREE ... )

LEAF ::= () | SIMPLE | STRING | VECTOR

(define make-parent list)

(define adopt cons)

(define the-empty-tree '())

(define (leaf? val) (not (pair? val)))

(define empty-tree? null?)
(define parent? list?)

(define left car)
(define but-left cdr)

(define (depth tree)
   (cond ((empty-tree? tree) 1)
         ((leaf? tree) 1)
         ((parent? tree)
            (max (+ 1 (depth (left tree)))
                (depth (but-left tree))))
         (else (error "bad input" depth tree))))

(define (flatten tree)
   (cond ((empty-tree? tree) '())
         ((leaf? tree) (list tree))
         ((parent? tree)
            (append (flatten (left tree))
                   (flatten (but-left tree))))
         (else (error "bad input" flatten tree)))

(define (tree-sub old-item new-item tree)
   (cond
      ((equal? old-item tree) new-item)
      ((empty-tree? tree) tree)
      ((leaf? tree) tree)
      ((parent? tree)
         (adopt
            (tree-sub old-item new-item (left tree))
            (tree-sub
               old-item new-item (but-left tree))))
      (else (error "bad input" tree-sub tree))))

(tree-rem b (a b c))
(adopt a (tree-rem b (b c)))
(adopt a (adopt (tree-rem b b) (tree-rem b (c))))
(adopt a (adopt () (tree-rem b (c))))
(adopt a (adopt () (adopt c ())))
(adopt a (adopt () (c)))
(adopt a (() c))
(a () c)

(define (tree-rem item tree)
   (cond
      ((equal? item tree) the-empty-tree)
      ((empty-tree? tree) tree)
      ((leaf? tree) tree)
      ((parent? tree)
         (if (equal? item (left tree)
            (tree-rem item (but-left tree))
            (adopt (tree-rem item (left tree))
                   (tree-rem item (but-left tree)))))
      (else (error "bad input" tree-rem tree))))

|(depth t)| = O(2ⁿ)
|(flatten t)| = O(2ⁿ)

[(depth t)] = O(2ⁿ)
[(flatten t)] = O(2ⁿ)

(define (lazy-small? promise)
   (define delta 1e-20)
   (<= (abs (force promise)) delta))

(define (lazy-cube promise)
   (* (force promise)
      (force promise)
      (force promise)))

(let ((value '())
      (first-time #t))
   (lambda ()
      (if first-time
         (begin
            (set! value (exp 1000))
            (set! first-time #f)))
      value)))

(define (lazy-switch key case1 case2 case3)
   (define key-val (force key))
   (cond ((< key-val 0) (force case1))
         ((even? key-val) (force case2))
         (else (force case2))))

STREAM ::= $() | (HEAD . {TAIL})

(define head car)
(define the-empty-stream '())
(define empty-stream? null?)

(define (tail stream) (force (cdr stream)))

(define (cons-stream head tail)
   (cons head (delay tail))) // error!

(define (stream-ref stream n)

   (define (unsafe-stream-ref stream n) ???)

   (if (and (natural? n) (stream? stream))
       (unsafe-stream-ref stream n)
       (error "bad input(s)" stream-ref stream n)))

(define (unsafe-stream-ref stream n)
   (cond
      ((empty-stream? stream)
         (error "out of range" stream-ref n))
      ((zero? n) (head stream))
      (else (unsafe-stream-ref
            (tail stream)
            (- n 1)))))

(do ((count n (- count 1))
    (members stream (tail members)))
    ((or (zero? count) (empty-stream? members))
      (if (empty-stream? members)
           (error "out of range" stream-ref n)
          (head members))))

(define (list->stream vals)
   (if (null? vals)
       the-empty-stream
       (cons-stream
         (car vals)
         (list->stream (cdr vals)))))

(define (unsafe-stream-map amp msgs)
   (if (empty-stream? msgs)
       the-empty-stream
       (cons-stream
         (amp (head msgs))
         (unsafe-stream-map amp (tail msgs)))))

(define (unsafe-stream-filter noise? msgs)
   (cond
      ((empty-stream? msgs) the-empty-stream)
      ((noise? (head msgs))
         (unsafe-stream-filter noise? (tail msgs)))
      (else (cons-stream
               (head msgs)
               (unsafe-stream-filter
                  noise?
                  (tail msgs))))))

(define (m-to-n m n)
   (if (> m n)
       the-empty-stream
       (cons-stream m (m-to-n (+ m 1) n))))

(m-to-n 3 5)
(cons-stream 3 (m-to-n 4 5))
(cons-stream 3 (cons-stream 4 (m-to-n 5 5)))
(cons-stream 3
   (cons-stream 4 (cons-stream 5 (m-to-n 6 5))))
(cons-stream 3 (cons-stream 4 (cons-stream 5 $())))
(cons-stream 3 (cons-stream 4 $(5)))
(cons-stream 3 $(4 5))
$(3 4 5)

(m-to-n 3 5)
(cons-stream 3 (m-to-n 4 5))
(3 . {(m-to-n 4 5)})

(define (from-m m)
   (cons-stream m (from-m (+ m 1))))