For these exercises, remember that your purpose statement, including its invariant, is at least as important as your function definition.
When you are called on, please copy your solution into one of the following pages:
A Bintree is one of -- (leaf-node Number) -- (tree-node Number Bintree Bintree)Design a function called tree-with-leaf-sums which, given a Bintree, returns a Bintree like the original, except that each leaf node is replaced by the sum of all the numbers on the path from the root to the leaf.
Example: #(struct:tree-node 3 #(struct:tree-node 4 #(struct:leaf-node 5) #(struct:leaf-node 10)) #(struct:leaf-node 2)) => #(struct:tree-node 3 #(struct:tree-node 4 #(struct:leaf-node 12) ; 3 + 4 + 5 = 12 #(struct:leaf-node 17)) ; 3 + 4 + 10 = 17 #(struct:leaf-node 5)) ; 3 + 2 = 5
A Bintree is one of -- Number -- (list Number Bintree Bintree)
Here we are using a list in place of a struct, like we do in ps06. In this representation, the tree in the example above would be represented (in write output mode) by:
(3 (4 12 17) 5)
A Tree is a -- (make-tree Number ListOfTree) A ListOfTree is one of -- empty -- (cons Tree ListOfTree)For these trees, we define a leaf to be a tree with an empty list of daughters.
EXAMPLE: Say there are 4 points on the route, called A, B, C, and D. D is the destination. The distance from A to B is 10, from B to C is 2, and from C to D is 5. For this route, the input to your function is the list (10 2 5) and your function should return the list (0 10 12 17)
;; A Count is a Positive Integer (define-struct rep (value count)) ;; A Rep is a (make-rep Integer Count) ;; (rep v c) represents the list (v v v v v ..) c copies of v ;; compress : ListOfInteger -> ListOfRep ;; Compresses the given input by replacing each run of consecutive v's ;; by (rep v k) ;; EXAMPLES: ;; () => () ;; (30 30 20 20 20 20 50 30 30) => ;; (list (make-rep 30 2) (make-rep 20 4) (make-rep 50 1) (make-rep 30 2))
You'll need a help function. Make sure you give a suitable contract, purpose statement, and invariants for your help function.
Last modified: Wed Nov 4 21:06:23 Eastern Standard Time 2015