### 3Design with Accumulators

#### 3.1Structural Problems

 #lang racket (require rackunit);; [Listof Number] -> [Listof Number];; Given a list of relative distances (lord), ;; produce a list of absolute distances;; EXAMPLE: given (1 10 3 7), produce (1 11 14 21)(define (absolute lord)  (cond    [(empty? lord) ’()]    [else (cons (first lord)                (add2all (first lord)                         (absolute (rest lord))))]));; Number [Listof Number] -> [Listof Number];; add n to all numbers on lon (define (add2all n lon)  (cond    [(empty? lon) ’()]    [else (cons (+ (first lon) n) (add2all n (rest lon)))]))(check-equal? (absolute ’(1 2 3)) ’(1 3 6))(check-equal? (absolute ’(1 10 3 7)) ’(1 11 14 21))

Figure 9: Absolute and relative distances (structurally)

 #lang racket(require rackunit);; [Tree Atom] is one of: ;; – Atom;; – (list [Tree Atom] [Tree Atom]);; DEF: The distance of an atom to the root of the tree is ;; the number of cons to be traversed to reach the atom. ;; [Tree Symbol] -> [Tree Number];; replace each symbol by its distance to the root of the tree ;; EXAMPLE: given (list ’a (list ’a ’b));; produce (list 1 (list 2 2));; ;; GRAPHICALLY:;;;; * *;; / \ / \;; a * ===> 1 *;; / \ / \;; a b 2 2(define (replace-height t)  (cond    [(symbol? t) 0]    [else       (list        (push1* (replace-height (first t)))        (push1* (replace-height (second t))))]));; [Tree Number] -> [Tree Number];; add 1 to all numbers in the tree(define (push1* t)  (cond    [(number? t) (add1 t)]    [else (list (push1* (first t)) (push1* (second t)))]))(check-equal? (replace-height (list ’a (list ’a ’b)))              (list 1 (list 2 2)))

Figure 10: Trees and their depth (structurally)

#### 3.2Accumulators

 #lang racket(require rackunit);; [Listof Number] -> [Listof Number];; Given a list of relative distances (lord), ;; produce a list of absolute distances;; EXAMPLE: given (1 10 3 7), produce (1 11 14 21)(define (absolute lord0)  ;; [Listof Number] Number -> [Listof Number]  ;; accumulator: so-far is the distance between lord0 and lord  (define (absolute lord so-far)    (cond      [(empty? lord) ’()]      [else (let ([d (+ (first lord) so-far)])              (cons d (absolute (rest lord) d)))]))  ;; – IN –   (absolute lord0 0))(check-equal? (absolute ’(1 2 3)) ’(1 3 6))(check-equal? (absolute ’(1 10 3 7)) ’(1 11 14 21))

Figure 11: Absolute and relative distances (accumulated)

 #lang racket(require rackunit);; [Tree Atom] is one of: ;; – Atom;; – (list [Tree Atom] [Tree Atom]);; DEF: The distance of an atom to the root of the tree is ;; the number of cons to be traversed to reach the atom. ;; [Tree Symbol] -> [Tree Number];; replace each symbol by its distance to the root of the tree ;; EXAMPLE: given (list ’a (list ’a ’b));; produce (list 1 (list 2 2));; ;; GRAPHICALLY:;;;; * *;; / \ / \;; a * ===> 1 *;; / \ / \;; a b 2 2(define (replace-height t0)  ;; [Tree Symbol] Number -> [Tree Number]  ;; accumulator: depth is distance of t to root of t0  (define (replace-height t depth)    (cond      [(symbol? t) depth]      [else (list (replace-height (first t) (+ depth 1))                   (replace-height (second t) (+ depth 1)))]))  ;; – IN –   (replace-height t0 0))(check-equal? (replace-height (list ’a (list ’a ’b)))              (list 1 (list 2 2)))

Figure 12: Trees and their depth (accumulated)