这次回顾HW2 Extra Practice Problems，主要是一些数据结构的练习。

课程主页：

https://www.coursera.org/learn/programming-languages-part-b/home

B站搬运：

https://www.bilibili.com/video/BV1tZ4y1D7

习题内容：

https://www.coursera.org/learn/programming-languages-part-b/supplement/EtJIy/extra-practice-problems

参考资料：

https://www.coursera.org/learn/programming-languages-part-b/discussions/weeks/2/threads/6dEq9JuDQUqRKvSbgyFKuw

代码

#lang racket
(provide (all-defined-out)) ;; so we can put tests in a second file

(struct btree-leaf () #:transparent)
(struct btree-node (value left right) #:transparent)

; 1
(define (tree-height tree)
  (cond [(btree-leaf? tree) 0]
        [#t (+ 1 (max (tree-height (btree-node-left tree))
                      (tree-height (btree-node-right tree))))]))

; 2
(define (sum-tree tree)
  (cond [(btree-leaf? tree) 0]
        [#t (+ (btree-node-value tree)
               (sum-tree (btree-node-left tree))
               (sum-tree (btree-node-right tree)))]))

; 3
(define (prune-at-v tree v)
  (cond [(btree-leaf? tree) tree]
        [(= v (btree-node-value tree)) (btree-leaf)]
        [#t (btree-node (btree-node-value tree)
                        (prune-at-v (btree-node-left tree) v)
                        (prune-at-v (btree-node-right tree) v))]))

; 4
(define (well-formed-tree? tree)
  (cond [(btree-leaf? tree) #t]
        [(btree-node? tree) (and (well-formed-tree? (btree-node-left tree))
                                 (well-formed-tree? (btree-node-right tree)))]
        [#t #f]))

; 5
(define (fold-tree f acc tree)
  (cond [(btree-leaf? tree) acc]
        [#t (let* ([v (f acc (btree-node-value tree))]
                   [v (fold-tree f v (btree-node-left tree))]
                   [v (fold-tree f v (btree-node-right tree))])
         v)]))

; 6
(define (fold-tree-curried)
  (lambda (f)
    (lambda (acc)
      (lambda (tree)
        (cond [(btree-leaf? tree) acc]
              [#t (let* ([v (f acc (btree-node-value tree))]
                         [v (fold-tree f v (btree-node-left tree))]
                         [v (fold-tree f v (btree-node-right tree))])
               v)])))))

; 7
(define (crazy-sum arr)
  (define (f op res arr)
    (cond [(null? arr) res]
          [#t (let ([v (car arr)])
                   (cond [(number? v) (f op (op res v) (cdr arr))]
                         [#t (f v res (cdr arr))]))]))
  (f + 0 arr))

; 8
(define (fold-list f acc arr)
  (cond [(null? arr) acc]
        [#t (fold-list f (f acc (car arr)) (cdr arr))]))

(define (either-fold f acc data)
  (define (g data)
    (cond [(list? data) fold-list]
          [(or (btree-leaf? data) (btree-node? data)) fold-tree]
          [#t (error (format "datatype is not list or tree: ~v" data))]))
  (let ([proc (g data)])
       (proc f acc data)))

; 9
(define (flatten arr)
  (define (f arr res)
    (cond [(null? arr) res]
          [#t (let ([v (car arr)])
                   (cond [(number? v) (f (cdr arr) (append res (list v)))]
                         [#t (f (cdr arr) (f v res))]))]))
  (f arr (list)))

测试

; https://www.coursera.org/learn/programming-languages-part-b/discussions/weeks/2/threads/6dEq9JuDQUqRKvSbgyFKuw

#lang racket

(require rackunit)
(require "hw5_extra.rkt")

(define t1 (btree-node 5 (btree-leaf) (btree-leaf))) ; one node

(define t2
  (btree-node 5 (btree-node 3 (btree-node 1 (btree-node 5 (btree-leaf) (btree-leaf)) (btree-leaf)) (btree-leaf)) (btree-leaf))) ; 5-3-1-5 all left nodes

;          t3
;
;          7
;         / \
;        3   2
;       / \ / \
;      9  2 1  3
;             / \
;            1   3
;                 \
;                 11
(define t3
  (btree-node 7 (btree-node 3 (btree-node 9 (btree-leaf) (btree-leaf)) (btree-node 2 (btree-leaf) (btree-leaf)))
              (btree-node 2 (btree-node 1 (btree-leaf) (btree-leaf))

                          (btree-node 3 (btree-node 1 (btree-leaf) (btree-leaf)) (btree-node 3 (btree-leaf) (btree-node 11 (btree-leaf) (btree-leaf)))))))

; ============== TESTS ================
(define tests
  (test-suite
   "Sample tests for Extra practice 2"
   
   ; tree height test
   (check-equal? (tree-height t1) 1 "Tree height test 1")
   (check-equal? (tree-height t2) 4 "Tree height test 2")
   (check-equal? (tree-height t3) 5 "Tree height test 3")

   ; tree sum test
   (check-equal? (sum-tree t1) 5 "Sum tree test 1")
   (check-equal? (sum-tree t2) 14 "Sum tree test 2")
   (check-equal? (sum-tree t3) 42 "Sum tree test 3")

   ; prune test
   (check-equal? (prune-at-v t1 5) (btree-leaf) "Prune test 1")
   (check-equal? (prune-at-v t1 6) t1 "Prune test 2")
   (check-equal? (prune-at-v t2 5) (btree-leaf) "Prune test 3")
   (check-equal? (prune-at-v t2 1) (btree-node 5 (btree-node 3 (btree-leaf) (btree-leaf)) (btree-leaf)) "Prune test 4")
   (check-equal? (prune-at-v t3 1111) t3 "Prune test 5")
   (check-equal? (prune-at-v t3 3) (btree-node 7 (btree-leaf) (btree-node 2 (btree-node 1 (btree-leaf) (btree-leaf)) (btree-leaf))) "Prune test 6")

   ; well formed test
   (check-equal? (well-formed-tree? t1) #t "Well formed test 1")
   (check-equal? (well-formed-tree? t2) #t "Well formed test 2")
   (check-equal? (well-formed-tree? t3) #t "Well formed test 3")
   (check-equal? (well-formed-tree? (btree-node 4 5 (btree-leaf))) #f "Well formed test 4")

   ; tree fold
   (check-equal? (fold-tree (lambda (x y) (+ x y 1)) 7
                            (btree-node 4 (btree-node 5 (btree-leaf) (btree-leaf)) (btree-leaf))) 18 "Tree fold test 1")

   ; tree fold-curried
   (check-equal? ((((fold-tree-curried) (lambda (x y) (+ x y 1))) 7)
                            (btree-node 4 (btree-node 5 (btree-leaf) (btree-leaf)) (btree-leaf))) 18 "Tree fold-curried test 1")


   ; crazy sum
   (check-equal? (crazy-sum (list 10 * 6 / 5 - 3)) 9 "Crazy sum test 1")
   (check-equal? (crazy-sum (list 1 1 1 1)) 4 "Crazy sum test 2")
   (check-equal? (crazy-sum (list 5 1 * 6)) 36 "Crazy sum test 3")

   ; either fold
   (check-equal? (either-fold (lambda (x y) (+ x y 1)) 7
                            (btree-node 4 (btree-node 5 (btree-leaf) (btree-leaf)) (btree-leaf))) 18 "Either fold test 1")
   (check-equal? (either-fold (lambda (x y) (+ x y)) 0 (list 1 2 3)) 6 "Either fold test 2")

   ; flatten
   (check-equal? (flatten (list 5 1 6)) (list 5 1 6) "Flatten test 1")
   (check-equal? (flatten null) null "Flatten test 2")
   (check-equal? (flatten (list 5 (list 1 2 3) 6)) (list 5 1 2 3 6) "Flatten test 3")
   (check-equal? (flatten (flatten (list 1 2 (list (list 3 4) 5 (list (list 6) 7 8)) 9 (list 10)))) (list 1 2 3 4 5 6 7 8 9 10) "Flatten test 4")
   
   ))

(require rackunit/text-ui)
;; runs the test
(run-tests tests)

测试结果：

27 success(es) 0 failure(s) 0 error(s) 27 test(s) run