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

### 代码

#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