;; A deepList is either: ;; * empty, or ;; * (cons s adl) where a is a symbol or a deepList and adl is a deepList ;; Note that there are two "back arrows" (self-references) to deepList in this case ;; Examples (define dl0 '(a)) (define dl1 '(()) ) (define dl2 '((a) ((b)))) (define dl3 '((a ((b c)) d (e)) ((f) ((g))))) (define dl4 '()) ;; ;; Template for deepList #| (define (f ... dl ... ) (cond [(empty? dl) ... ] [(cons? d1) (cond [(symbol? (first dl)) ... (first dl) ... (f (rest dl)) ...)] [(cons? (first dl)) ... (f (first dl)) ... (f (rest dl))])])) ;; Note that the template contains two recursive calls on f in this case! |# ;; flatten: deepList -> symbol-list ;; Purpose: (flatten dl) consumes a deepList dl and concatenates all of ;; the symbols embedded in dl into a symbol-list where the symbols appear ;; in the same order as when dl is printed as string. ;; input to form a list of elements ;; Examples: (check-expect (flatten dl0) '(a)) (check-expect (flatten dl1) empty) (check-expect (flatten dl2) '(a b)) (check-expect (flatten dl3) '(a b c d e f g)) (check-expect (flatten dl4) empty) ;; Template Instantiation for flatten: #| (define (flatten dl) (cond [(empty? dl) ... ] [(cons? d1) (cond [(empty? (first dl)) ... (flatten (rest dl))] [(symbol? (first dl)) ... (first dl) ... (flatten (rest dl)))] [(cons? (first dl)) ... (flatten (first dl)) ... (flatten (rest dl))])])) |# ;; Code: (define (flatten dl) (cond [(empty? dl) empty] [(cons? dl) (cond [(empty? (first dl)) (flatten (rest dl))] [(symbol? (first dl)) (cons (first dl) (flatten (rest dl)))] [(cons? (first dl)) (append (flatten (first dl)) (flatten (rest dl)))])])) ;;fastFlatten deepList -> symbol-list ;; Purpose: (fastFlatten dl) consumes a deepList dl and concatenates all of ;; the symbols embedded in dl into a symbol-list where the symbols appear ;; in the same order as when dl is printed as string. ;; input to form a list of elements ;; Examples: (check-expect (fastFlatten dl0) '(a)) (check-expect (fastFlatten dl1) empty) (check-expect (fastFlatten dl2) '(a b)) (check-expect (fastFlatten dl3) '(a b c d e f g)) (check-expect (flatten dl4) empty) ;; Template Instantiation for fastFlatten: #| (define (fastFlatten dl) ... (fastFlattenHelp dl empty) ...) (define (fastFlattenHelp dl accum) (cond [(empty? dl) ... ] [(cons? d1) (cond [(empty? (first dl)) ... (fastFlattenHelp (rest dl) ...) ...] [(symbol? (first dl)) ... (first dl) ... (fastFlattenHelp (rest dl) ... ) ... ] [(cons? (first dl)) ... (fastFlattenHelp (first dl) (fastFlattenHelp (rest dl) accum)])])) ;; Note that the two calls on fastFlattenHelp involve nesting |# (define (fastFlatten dl) (fastFlattenHelp dl empty)) (define (fastFlattenHelp dl accum) (cond [(empty? dl) accum ] [(cons? dl) (cond [(empty? (first dl)) (fastFlattenHelp (rest dl) accum)] [(symbol? (first dl)) (cons (first dl) (fastFlattenHelp (rest dl) accum))] [(cons? (first dl)) (fastFlattenHelp (first dl) (fastFlattenHelp (rest dl) accum))])]))