CS Musings

;; 2.17
(define (last-pair lst)
  (if (null? (rest lst))
      lst
      (last-pair (rest lst))))
(last-pair (list 23 72 149 34))
 
;; 2.18
(define (reverse lst)
  (define (iter orig new)
    (if (null? orig)
        new
        (iter (rest orig) (cons (first orig) new))))
  (iter lst empty))
(reverse (list 1 4 9 16 25))
 
;; 2.19
(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))
 
(define (cc amount coin-values)
  (cond [(= amount 0) 1]
        [(or (< amount 0)(no-more? coin-values)) 0]
        [else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values))]))
 
(define (no-more? lst) (null? lst))
(define (except-first-denomination lst) (cdr lst))
(define (first-denomination lst) (first lst))
(cc 100 us-coins)
 
;; 2.20
(define (same-parity f . r)
  (let ((parity (if (even? f) even? odd?)))
    (define (list-parity lst)
      (cond [(null? lst) empty]
            [(parity (first lst)) (cons (first lst) (list-parity (rest lst)))]
            [else (list-parity (rest lst))]))
    (list-parity (cons f r))))
(same-parity 1 2 3 4 5 6 7)
 
;; 2.21
(define (square-list-rec items)
  (if (null? items)
      empty
      (cons (sqr (first items)) (square-list-rec (rest items)))))
(square-list-rec (list 1 2 3 4))
(define (square-list-map items)
  (map sqr items))
(square-list-map (list 1 2 3 4))
 
;; 2.23
(define (for-each fun items)
  (define (run)
    (fun (car items))
    (for-each fun (cdr items)))
  (if (null? items)
      #t
      (run)))
(for-each (lambda (x) (newline) (display x))
          (list 57 321 88))
 
;; 2.24: (1 (2 (3 4)))
 
;; 2.25
(car (cdr (car (cdr (cdr (list 1 3 (list 5 7) 9))))))
(car (car (list (list 7))))
(define complex (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr complex))))))))))))
 
;; 2.26
(define x (list 1 2 3))
(define y (list 4 5 6))
(append x y) ;-> (1 2 3 4 5 6)
(cons x y) ;-> ((1 2 3) 4 5 6)
(list x y) ;-> ((1 2 3) (4 5 6))
 
;; 2.27
(define (deep-reverse lst)
  (define (iter orig new)
    (cond [(null? orig) new]
          [(pair? (first orig)) (iter (rest orig) (cons (deep-reverse (first orig)) new))]
          [else (iter (rest orig) (cons (first orig) new))]))
  (iter lst empty))
(define x (list (list 1 2) (list 3 4)))
x
(reverse x)
(deep-reverse x)
 
;; 2.28
(define (fringe tree)
  (cond [(null? tree) empty]
        [(not (pair? tree)) (list tree)]
        [else (append (fringe (car tree)) (fringe (cdr tree)))]))
(fringe x)
(fringe (list x x))
 
;; 2.29
(define (make-mobile left right)
  (list left right))
 
(define (make-branch length structure)
  (list length structure))
 
;a)
(define (left-branch mobile)
  (car mobile))
(define (right-branch mobile)
  (car (cdr mobile)))
(define (branch-length branch)
  (car branch))
(define (branch-structure branch)
  (car (cdr branch)))
 
;b)
(define (total-weight mobile)
  (cond [(not (pair? mobile)) mobile]
        [else (+ (total-weight (branch-structure (left-branch mobile)))
                 (total-weight (branch-structure (right-branch mobile))))]))
 
;c)
 
;; 2.30
(define test-tree (list 1
                        (list 2 (list 3 4) 5)
                        (list 6 7)))
(define (square-tree tree)
  (cond [(null? tree) null]
        [(pair? (car tree)) (cons (square-tree (car tree)) (square-tree (cdr tree)))]
        [else (cons (sqr (car tree)) (square-tree (cdr tree)))]))
(square-tree test-tree)
 
(define (square-tree-map tree)
  (map (lambda (x)
         (if (pair? x)
             (square-tree-map x)
             (sqr x))) tree))
(square-tree-map test-tree)
 
;; 2.31
(define (tree-map fun tree)
  (map (lambda (x)
         (if (pair? x)
             (tree-map fun x)
             (fun x))) tree))
(tree-map sqr test-tree)
 
;; 2.33
(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))
 
(define (my-map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) empty sequence))
 
(define (append seq1 seq2)
  (accumulate cons seq2 seq1))
 
(define (length sequence)
  (accumulate (lambda (x y) (+ 1 y)) 0 sequence))
(length (list 1 2 3 4 5))
 
;; 2.34
(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) (+ this-coeff (* x higher-terms)))
              0
              coefficient-sequence))
(horner-eval 2 (list 1 3 0 5 0 1))
 
;; 2.35
;; enumerate-tree in book:
(define (enumerate-tree tree)
  (cond [(null? tree) empty]
        [(not (pair? tree)) (list tree)]
        [else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree)))]))
 
(define (count-leaves t)
  (accumulate + 0 (map (lambda (x) 1) (enumerate-tree t))))
(count-leaves (list x x))
 
;; 2.36
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      empty
      (cons (accumulate op init (map first seqs))
            (accumulate-n op init (map rest seqs)))))
"2.36"
(accumulate-n + 0 '((1 2 3) (4 5 6) (7 8 9) (10 11 12)))
 
;; 2.37
(define (dot-product v w)
  (accumulate + 0 (map * v w)))