;; The first three lines of this file were inserted by DrRacket. They record metadata ;; about the language level of this file in a form that our tools can easily process. #reader(lib "htdp-intermediate-reader.ss" "lang")((modname lect27-ancestor-tree) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ()))) ; data def'n: ; an anc-tree (ancestor tree) is: ; - 'unknown ; - (make-child [string] [int] [symbol] [anc-tree] [anc-tree]) (define-struct child (name yob eye ma pa)) ; examples of AncTrees: 'unknown (make-child "Abe" 1901 'brown 'unknown 'unknown) (make-child "Homer" 1949 'brown 'unknown (make-child "Abe" 1901 'brown 'unknown 'unknown)) (define (func-for-ancTree tr) (cond [(symbol? tr) ...] [(child? tr) (...(child-name tr) ...(child-yob tr) ...(child-eye tr) ...(func-for-ancTree (child-ma tr)) ...(func-for-ancTree (child-pa tr)) )])) (check-expect (size 'unknown) 0) (check-expect (size (make-child "Abe" 1901 'brown 'unknown 'unknown)) 1) (check-expect (size (make-child "Homer" 1949 'brown 'unknown (make-child "Abe" 1901 'brown 'unknown 'unknown))) 2) ; examples of data of anc-tree: 'unknown (define abe (make-child "Abe" 1920 'blue 'unknown 'unknown)) (define mona (make-child "Mona" 1929 'brown 'unknown 'unknown)) (make-child "homer" 1955 'brown (make-child "Mona" 1929 'brown 'unknown 'unkown) (make-child "Abe" 1920 'blue 'unknown 'unknown)) (define jackie (make-child "Jackie" 1926 'brown 'unknown 'unknown)) (define marge (make-child "Marge" 1956 'blue jackie 'unknown)) (define homer (make-child "Homer" 1955 'brown mona abe)) (define bart (make-child "Bart" 1979 'brown marge homer)) ; Write the template for a function to process an Anc-Tree: ; unknown? ANY -> boolean ; Is x [a representation of] the unknown Anc-Tree? ; (define (unknown? x) (equal? x 'unknown)) ; why not symbol? why not symbol=? ; ; Cf.: and example of using and/f: ; (define unknown? (and/f symbol? (λ (s) (symbol=? s 'unknown)))) ;; fun-for-anc-tree : anc-tree --> ??? ;; ;(define (fun-for-anc-tree anc) ; (cond [(unknown? anc) ...] ; [(child? anc) ...(child-name anc) ; ...(child-yob anc) ; ...(child-eye anc) ; ...(fun-for-anc-tree (child-ma anc)) ; ...(fun-for-anc-tree (child-pa anc))]) ; change-name : anc-tree -> anc-tree ; (define (change-name anc name1 name2) (cond [(unknown? anc) 'unknown] [(child? anc) (make-child (if (string=? (child-name anc) name1) name2 (child-name anc)) (child-yob anc) (child-eye anc) (change-name (child-ma anc) name1 name2) (change-name (child-pa anc) name1 name2))])) ; size : Anc-tree -> natnum ; (define (size anc) (cond [(symbol? anc) 0] [(child? anc) (+ (size (child-ma anc)) (size (child-pa anc)) 1)])) (check-expect (size 'unknown) 0) (check-expect (size jackie) 1) (check-expect (size marge) 2) (check-expect (size homer) 3) (check-expect (size bart) 6) ; rename-all : anc-tree string -> anc-tree ; (define (rename-all anc newname) (cond [(unknown? anc) 'unknown] [(child? anc) (make-child newname (child-yob anc) (child-eye anc) (rename-all (child-ma anc) newname) (rename-all (child-pa anc) newname))])) ; all-names : anc-tree -> (listof string) ; Return a list of all the names in a tree. ; ;; (define (all-names anc) (cond [(unknown? anc) empty] [(child? anc) (append (all-names (child-ma anc)) (list (child-name anc)) (all-names (child-pa anc)))])) ; all-childs : anc-tree -> (listof child) ; Return a list of all the childs in a tree. ; ;; (define (all-childs anc) (cond [(unknown? anc) empty] [(child? anc) (append (all-childs (child-ma anc)) (list anc) (all-childs (child-pa anc)))])) (check-expect (all-childs 'unknown) empty) (check-expect (all-childs abe) (list abe)) (check-expect (all-childs homer) (list mona homer abe)) (check-expect (all-childs bart) (list jackie marge bart mona homer abe)) #| ; contains? : AncTree, string -> boolean ; Does the tree contain the given name, anywhere? ; (check-expect (contains? ... "Bart") ...) (check-expect (contains? bart "Bart") true) (check-expect (contains? bart "Homer") true) (check-expect (contains? bart "Abe") true) (check-expect (contains? homer "Bart") false) (check-expect (contains? bart "Marge") true) (check-expect (contains? bart "Mona") true) (check-expect (contains? mona "Bart") false) ; challenge: write my-append: list, list -> list ; (Hint: follow the template for a list, ; but only take first/rest of arg1.) ; any-time-travelers? : anc-tree -> boolean ; (anybody born before their parents?)(*) ; Return all time-travelers. ; (define (any-time-travelers? anc) (any-time-travelers-help? anc +inf.0)) ; child-born-before-yr-or-any-time-travelers? ; (define (any-time-travelers-help? anc parent-yob) (cond [(unknown? anc) false] [(child? anc) (or (> (child-yob anc) parent-yob) (any-time-travelers-help? (child-ma anc) (child-yob anc)) (any-time-travelers-help? (child-pa anc) (child-yob anc)))])) (check-expect (any-time-travelers? 'unknown) false) (check-expect (any-time-travelers? abe) false) (check-expect (any-time-travelers? (make-child "lexxor" 1801 "orange" (make-child "Scully" 1970 "brown" 'unknown 'unknown) 'unknown)) true) ; (*) Okay, if somebody was born before their parents, it means their *parents* ; were the time travelers. But for this exercise, we'll ignore that, ; and just return the child who was born before the parents. ; entitle: AncTree -> AncTree ; Add "Mr." in front of each father's name, and "Ms." to each mother's. ; (Cf. walking an html tree and making some transform.) ; ;; entitle : anc-tree --> anc-tree ;; (define (entitle anc) (entitle-help anc "Baby")) (define (entitle-help anc title-for-root) (cond [(unknown? anc) 'unknown] [(child? anc) (make-child (string-append title-for-root " " (child-name anc)) (child-yob anc) (child-eye anc) (entitle-help (child-ma anc) "Ms.") (entitle-help (child-pa anc) "Mr."))])) (check-expect (entitle 'unknown) 'unknown) (check-expect (entitle homer) (make-child "Baby Homer" 1951 'brown (make-child "Ms. Mona" 1929 'blue 'unknown 'unknown) (make-child "Mr. Abe" 1920 'brown 'unknown 'unknown))) #| /** How would we write this same data structure (and programs) in Java? */ abstract class AncTree { } class Unknown extends AncTree { } class Child extends AncTree { String name; int yob; // year-of-birth String eye; // eye-color, e.g. "brown" AncTree ma, pa; // mother, father /** standard constructor */ public Child( String _name, int _yob, String _eye, AncTree _ma, AncTree _pa ) { this.name = _name; this.yob = _yob; this.eye = _eye; this.ma = _ma; this.pa = _pa; } /** @Override */ public String toString( /* Child this */ ) { return "new Child" + "( " + this.name.toString() + ", " + this.yob + ", " + this.eye.toString() + ", " + this.ma.toString() + ", " + this.pa.toString() + " )"; } public static void main( String[] args ) { AncTree abe = new Child( "Abe", 1920, "brown", new Unknown(), new Unknown() ); AncTree mona = new Child( "Mona", 1929, "blue", new Unknown(), new Unknown() ); AncTree homer = new Child( "Homer", 1951, "brown", mona, abe ); System.out.println( "Actual: " + abe.toString() ); System.out.println( "Expect: " + "new Child( \"Abe\", 1920, \"brown\", new Unknown(), new Unknown() )" ); System.out.println( "Actual: " + homer.toString() ); System.out.println( "Expect: " + "??" ); } } |# ; anctree->string: ;(check-expect (anctree->string abe) "[? Abe ?]") ;(check-expect (anctree->string abe) "new Child(Abe,") ;(check-expect (anctree->string abe) "new Child(Abe,") ; Mon: Define anc-tree. examples; template; size; all-names ; ; Wed: ; q: more examples of using map (w/ lambda) ; qz: what is the data-def'n of a FamTree ; self-quiz: toString ; start Java version of famTree ; ; Fri: ; Write: change-all-names (add a "Mr" or "Ms" to each name) ; ; Java: write `size` ; Note: the analog to `cond` is handled by the OO, which is good. ; If you're ever using 'instanceof' or using 'if ...== null', it's not really OO. ; Java: write `allNames` ; term: "composite design pattern" ; Java: write change-all-names ; ; Writing `equals` (in racket, then in Java) is interesting, ; -- especially ; ; ...backquote ; ...desc tree? No. Directories? ; ...parsing? Lang def? |#