3 Design with Accumulators
3.1 Structural 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))
#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)))
3.2 Accumulators
#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))
#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)))
3.3 One Function per Task
#lang racket
(require rackunit)
;; [Listof Symbol] -> [Listof Number]
;; replace the symbols in los0 with the frequency of occurrence
;; EXAMPLE: given ’(a b c a a) produce ’(3 1 1 3 3)
(define (frequency-transform los0)
;; intermediate data structures use hash tables as an
;; intermediary data structure: FREQS = [Hash Symbol Number]
;; [Listof Symbol] FREQS -> FREQS
;; collect the frequencies at which symbols occur
;; accumulator: h counts occurrences of symbols
;; between los and los0
(define (freq los h)
(cond
[(empty? los) h]
[else
(freq (rest los) (hash-update h (first los) add1 0))]))
;; [Listof Symbol] FREQS -> [Listof Number]
;; replace symbols in l with their frequencies from h
(define (replace l h)
(cond
[(empty? l) ’()]
[else
(cons (hash-ref h (first l)) (replace (rest l) h))]))
;; – IN –
(define frequency-of-occurrence (histogram los0 #hash()))
;; – RETURN –
(replace los0 frequency-of-occurrence))
(check-equal? (frequency-transform ’(a b c a a)) ’(3 1 1 3 3))