;; 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))])]))