RECURSION: Turtles all the way down ----------------------------------- Matrioshka doll ;; (self-referential definitions) ;; Matrioshka dolls ;; what do you need to represent the innermost doll? ;; ATOMIC data (define-struct dress (contents)) ;; VERSION 1: A 4-layer Russian doll ;; A RD (Russian Doll) is one of: ;; -- 'solid ;; -- (make-dress 'solid) ;; ... ;; -- (make-dress (make-dress ..... 'solid)) ;; RD template: (define (rd-template rd) (cond [(symbol? rd) ...] [(symbol? (rd-contents rd)) ... (rd-contents rd) ...] [(symbol? (rd-contents (rd-contents rd))) ... (rd-contents rd) ...] [else ... (rd-contents rd) ...])) ;; RD -> number ;; count the number of layers of a Russian Doll (define (rd-layers rd) (cond [(symbol? rd) ...] ...)) ;; Our set is 10 layers. Tedious^2. ;; How about a thousand layers? Yikes. ;; The ivory ball at the Gugong Bowuguan -- 21 layers ;; VERSION 2: ;; +-------------------------------+ ;; | | ;; v | ;; A RD (Russian Doll) is one of: | ;; --- 'solid | ;; --- (make-dress RD) x-------------+ (circle the RD & draw arrow to RD) ;; HEY! Circular definition! Does this work? ;; Well... can we build examples? ;; examples of data 'solid ; Sure! (make-dress 'solid) ; Implied by 'solid (make-dress (make-dress 'solid)) ; Implied by (make-dress 'solid) (make-dress (make-dress (make-dress 'solid))) ; How far do you want to go? ;; Do the doll-layers function by the numbers. ;; template: (for the V2 data defn!) ;; doll-layers : RD -> Number #; (define (rd-template rd) (cond [(symbol? rd) ...] [(dress? rd) ... (rd-contents rd) ...])) ;; where is the BACK-ARROW??? ;; Use name of fun for backarrow. This is recursion! ;; (Add a (doll-layers []) around the (rd-contents rd), ;; circle the expression and draw an arrow back to the ;; (DOLL-LAYERS RD) on line 1. As below:) #; (define (rd-template rd) (cond [(symbol? rd) ...] [(dress? rd) ... (rd-template (dress-contents rd)) ...])) ;; now there is a backarrow in the function definition exactly ;; where there is a backarrow in the data definition. Isn't ;; this neat? ;; examples of function behavior ;; 'solid |-----> 0 ;; (make-dress 'solid) |-----> 1 ;; (make-dress (make-dress 'solid)) |-----> 2 ;; (make-dress (make-dress (make-dress 'solid))) |-----> 3 (define (doll-layers rd) (cond [(symbol? rd) 0] [(dress? rd) (+ (doll-layers (dress-contents rd)) 1)])) (check-expect (doll-layers 'solid) 0) (check-expect (doll-layers (make-dress 'solid)) 1) (check-expect (doll-layers (make-dress (make-dress 'solid))) 2) (check-expect (doll-layers (make-dress (make-dress (make-dress 'solid)))) 3)