;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; LAB 6 ;; ;; Solutions ;; ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Part 1: Data Definitions and Examples ;; ;;;; Code-tree Data Definition ;; A leaf is a ;; (make-leaf symbol number) (define-struct leaf (symbol weight)) ;; A code-tree is either a ;; --leaf, or ; (make-code-tree (listof symbols) number ; code-tree ; code-tree) (define-struct code-tree (symbols weight left right)) ;; and where the following two invariants hold ;; (a) For each node, the sum of the weights of the left subtree ;; plus the sum of the weights of the right subtree is ;; the weight of the node. ;; (b) For each node, the symbols in the list of symbols of the node are ;; all of the symbols occurring in leaves of the left subtree ;; and all of the symbols occurring in leaves of the right subtree. ;;;;;;;;;;;;;;;;;;;; ;;; Code-tree Examples from Part 1c and 1d (define tree-1 (make-code-tree '(A B C D E F G H) 8 (make-code-tree '(A B C D) 4 (make-code-tree '(A B) 2 (make-leaf 'A 1) (make-leaf 'B 1)) (make-code-tree '(C D) 2 (make-leaf 'C 1) (make-leaf 'D 1))) (make-code-tree '(E F G H) 4 (make-code-tree '(E F) 2 (make-leaf 'E 1) (make-leaf 'F 1)) (make-code-tree '(G H) 2 (make-leaf 'G 1) (make-leaf 'H 1))))) (define tree-2 (make-code-tree '(A B C D E F G H) 17 (make-leaf 'A 8) (make-code-tree '(B C D E F G H) 9 (make-code-tree '(B C D) 5 (make-leaf 'B 3) (make-code-tree '(C D) 2 (make-leaf 'C 1) (make-leaf 'D 1))) (make-code-tree '(E F G H) 4 (make-code-tree '(E F) 2 (make-leaf 'E 1) (make-leaf 'F 1)) (make-code-tree '(G H) 2 (make-leaf 'G 1) (make-leaf 'H 1)))))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Part 3: Encoding and Decoding ;; ;;;;;;;;;;;;;;;;;;;;;;;; ;;; Part 3a. Encoding ;; A bit is either 0 or 1 ;; encode: (list-of symbols) code-tree -> (list-of bits) ;; encode msg using ctree ;; (define (encode msg ctree) ... ) ;; Use structural recursion on msg (a list) (define (encode msg ctree) (cond [(empty? msg) empty] [else (append (encode-symbol (first msg) ctree) (encode (rest msg) ctree))])) ;; encod-symbol: symbol code-tree -> (list-of bits) ;; encode symbol using ctree ;; Use structural recursion on ctree (a code-tree) ;; NOTE: it is a good idea to produce an error message if ;; a problem arises. This will help you spot errors when testing (define (encode-symbol s ctree) (cond [(leaf? ctree) empty] [else (cond [(intree? s (code-tree-left ctree)) (cons 0 (encode-symbol s (code-tree-left ctree)))] [(intree? s (code-tree-right ctree)) (cons 1 (encode-symbol s (code-tree-right ctree)))] [else "encode-symbol: symbol not found on tree"])])) ;; intree?: symbol code-tree -> boolean ;; Does symbol occur in code-tree? By invariant (b) we need ;; only test symbols occuring at root of tree (define (intree? s ctree) (cond [(leaf? ctree) (symbol=? s (leaf-symbol ctree))] [else (ormap (lambda (t) (symbol=? s t)) (code-tree-symbols ctree))])) ;;;;;;;;;;;;;;;;;;;;;;;; ;;; Part 3b. Decoding ;; A bit is either 0 or 1 ;; decode: (list-of bits) code-tree -> (list-of symbols) ;; decode bits (list-of bits) using ctree ;; (define (decode bits ctree) ... ) ;;;; You can use structural recursion on bits and ctree simultaneously. ;;;; The trick is that you need to remember the original ctree, and ;;;; recurring on decode will forget this tree. Use local!! (define (decode bits ctree) (local ((define (decode-1 bits t) (cond [(and (leaf? t) (empty? bits)) (list (leaf-symbol t))] [(leaf? t) (cons (leaf-symbol t) (decode-1 bits ctree))] [(empty? bits) "decode: Out-of-bits before reaching a leaf."] [else (cond [(= 0 (first bits)) (decode-1 (rest bits) (code-tree-left t))] [(= 1 (first bits)) (decode-1 (rest bits) (code-tree-right t))] [else "decode: Not a bit."])]))) (decode-1 bits ctree))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Part 4: Building Code Trees ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Part 4a. Frequency Lists ;; An fpair is a ;; (make-fpair symbol weight) (define-struct fpair (symbol weight)) ;; create-leaves: (list-of fpair) -> (list-of leaf) ;; Create a list of leaves from list of fpairs ;; (define (create-leaves fpairs) ...) (define (create-leaves fpairs) (map (lambda (x) (make-leaf (fpair-symbol x) (fpair-weight x))) fpairs)) ;;; Examples: (define freq-1 (list (make-fpair 'A 1) (make-fpair 'B 1) (make-fpair 'C 1) (make-fpair 'D 1) (make-fpair 'E 1) (make-fpair 'F 1) (make-fpair 'G 1) (make-fpair 'H 1))) (define freq-2 (list (make-fpair 'C 1) (make-fpair 'D 1) (make-fpair 'E 1) (make-fpair 'F 1) (make-fpair 'G 1) (make-fpair 'H 1) (make-fpair 'B 3) (make-fpair 'A 8))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Part 4b. build-code-tree ;; build-code-tree: (list-of s-w-p) -> code-tree ;; return a code-tree based on fpairs giving the frequency of each symbol. ;; fpairs is sorted in increasing order of weight ;; (define (build-code-tree fpairs) ... ) (define (build-code-tree fpairs) (local ((define leaves (create-leaves fpairs))) (first (merge-trees leaves)))) ;; merge-trees: (list-of code-trees) -> (list-of code-trees) ;; Merge alocts as in step 2 of the algorithm in Part 1b ;; until alocts contains only one code-tree ;; INVARIANT: The alocts is sorted by increasing order of weight. ;; (define (merge-trees alocts)...) (define (merge-trees alocts) (cond ;; should not occur, unless original list is empty [(empty? alocts) "merge-trees: alocts is empty"] [(empty? (rest alocts)) alocts] [else (local ((define rest-alocts (rest (rest alocts))) ;; Step 2a: alocts is already sorted (define ct1 (first alocts)) (define ct2 (first (rest alocts))) ;;Step 2b: (define new-ctree (make-code-tree (append-syms ct1 ct2) (+ (get-wt ct1) (get-wt ct2)) ct1 ct2)) ;; Step 2c (define new-alocts (insert-tree new-ctree rest-alocts))) (merge-trees new-alocts))])) ;;;;;;;;;;;;;;;;;;;;;;; ;;;; Helper functions for merge-tree ;; append-syms: code-tree code-tree -> (list-of symbols) ;; append symbols in ct1 and ct2 into single list (define (append-syms ct1 ct2) (local ((define s1 (cond [(leaf? ct1) (list (leaf-symbol ct1))] [else (code-tree-symbols ct1)])) (define s2 (cond [(leaf? ct2) (list (leaf-symbol ct2))] [else (code-tree-symbols ct2)]))) (append s1 s2))) ;; get-wt: code-tree -> number ;; returns weight of tree (define (get-wt t) (cond [(leaf? t) (leaf-weight t)] [else (code-tree-weight t)])) ;; insert-tree: code-tree (list-of code-tree) -> (list-of code-tree) ;; insert ct into lcts ordered by weight (define (insert-tree ct lcts) (cond [(empty? lcts) (list ct)] [else (cond [(< (get-wt ct) (get-wt (first lcts))) (cons ct lcts)] [else (cons (first lcts) (insert-tree ct (rest lcts)))])])) ;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;