;; 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 ancestor-tree-start) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f () #f))) ; We want to represent ancestor-trees: ; ?? ?? ?? ?? ?? ?? ; \ / \ / \ / ; jackie.. ?? abe... mona... ; \ / \ / ; marge (b.1956, blue) homer (b.1955, brown) ; \ / ; bart (b.1979, brown eyes) ; Data Def'n: ; ; An anc-tree is: ; - 'unknown, OR ; - (make-child [string] [integer] [symbol] [anc-tree] [anc-tree]) (define-struct anc-tree (name yob eye ma pa)) 'unknown (make-child "jackie" 1917 'brown 'unknown 'unknown) (make-child "marge" 1956 'blue (make-child "jackie" 1917 'brown 'unknown 'unknown) 'unknown) ; 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 anc-trees: 'unknown (make-child "Jackie" 1926 'brown 'unknown 'unknown) (make-child "Marge" 1956 'blue (make-child "Jackie" 1926 'brown 'unknown 'unknown) 'unknown) ;;; Template ; func-for-anc-tree : anc-tree -> ??? ; (define (func-for-anc-tree tr) (cond [(symbol? tr) ...] [(child? tr) (...(child-name tr) ...(child-yob tr) ...(child-eye tr) ...(func-for-anc-tree (child-ma tr)) ...(func-for-anc-tree (child-pa tr))) ])) ; size : AncTree -> natnum ; Return the size of `tr` -- the number of `child`s it contains. ; (check-expect (size 'unknown) ...) (check-expect (size (make-child "jackie" 1917 'brown 'unknown 'unknown)) ...) (check-expect (size (make-child "marge" 1956 'blue (make-child "jackie" 1917 'brown 'unknown 'unknown) 'unknown)) ...) (define (size tr) (cond [(unknown? tr) 'YOUR-CODE-HERE] [(child? tr) 'YOUR-CODE-HERE ])) (check-expect (size 'unknown) 0) (check-expect (size (make-child "Abe" 1920 'brown 'unknown 'unknown)) 1) (check-expect (size (make-child "Homer" 1955 'brown 'unknown (make-child "Abe" 1920 'brown 'unknown 'unknown))) 2) ; examples of data, for anc-trees: '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 homer (make-child "Homer" 1955 'brown mona abe)) (define jackie (make-child "Jackie" 1926 'brown 'unknown 'unknown)) (define marge (make-child "Marge" 1956 'blue jackie 'unknown)) (define bart (make-child "Bart" 1979 'brown marge homer)) (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) ; unknown? ANY -> boolean ; Is x [a representation of] the unknown Anc-Tree? ; (define (unknown? x) (equal? x 'unknown)) ; why not symbol? why not symbol=? ;(define (unknown? x) (and (symbol? x) ; (symbol=? x 'unknown))) ; ; Cf.: and example of using and/f: ;(define unknown? (and/f symbol? (λ (s) (symbol=? s 'unknown)))) ; change-name : anc-tree string string -> anc-tree ; Return a tree like `anc`, but with every name `name1` replace with `name2` ; (define (change-name anc name1 name2) (cond [(unknown? anc) 'YOUR-CODE-HERE] [(child? anc) 'YOUR-CODE-HERE])) (check-expect (change-name 'unknown "Joseph" "Joey") 'unknown) (check-expect (change-name jackie "Joseph" "Joey") jackie) (check-expect (change-name jackie "Jackie" "Jack") (make-child "Jack" 1926 'brown 'unknown 'unknown)) (check-expect (change-name (make-child "Joseph" 50 'blue (make-child "Amy" 50 'blue (make-child "Joseph" 50 'blue 'unknown 'unknown) (make-child "Joey" 50 'blue 'unknown 'unknown)) (make-child "Joseph" 50 'blue 'unknown 'unknown)) "Joseph" "Joey") (make-child "Joey" 50 'blue (make-child "Amy" 50 'blue (make-child "Joey" 50 'blue 'unknown 'unknown) (make-child "Joey" 50 'blue 'unknown 'unknown)) (make-child "Joey" 50 'blue 'unknown 'unknown))) ; all-names : anc-tree -> (listof string) ; Return a list of all the names in a tree. ; (define (all-names anc) (cond [(unknown? anc) 'YOUR-CODE-HERE] [(child? anc) 'YOUR-CODE-HERE])) (check-expect (all-names 'unknown) '()) (check-expect (all-names jackie) (cons "Jackie" '()) ) (check-expect (sort (all-names marge) string<=?) (sort (cons "Jackie" (cons "Marge" '())) string<=?)) (check-expect (sort (all-names homer) string<=?) (sort (cons "Mona" (cons "Homer" (cons "Abe" '()))) string<=?)) (check-expect (sort (all-names bart) string<=?) (sort (cons "Jackie" (cons "Marge" (cons "Bart" (cons "Mona" (cons "Homer" (cons "Abe" '())))))) string<=?) ) ; LEFT AS PRACTICE: #| ; all-childs : anc-tree -> (listof child) ; Return a list of all the childs in a tree. ; (define (all-childs 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 (sort (map child-name (all-childs bart) string<=?)) (sort (map child-name (list jackie marge bart mona homer abe)) string<=?)) ; Hmm, we should really sort these, as before; ; we can easily make `child<=?` which just compares to childs based on name. ; OR, we could just extract the names, and sort those. ; (This is imperfect, but reasonable as a hack: if the anc-tree had two different people ; with the same name, and the result instead had one of those in its answer twice, ; we wouldn't catch that error. We might even assuage this a bit, by having a test-case ; with an anc-tree `j` containing only two people j1 and j2, both named "Joe", and asserting that ; (or (equal? (all-childs j) (list j1 j2)) ; (equal? (all-childs j) (list j2 j1))) ; ...though at that point you might as well just have made a `child<=?` and done it properly. |# ; LEFT AS AN EXERCISE: #| ; contains? : AncTree, string -> boolean ; Does the tree contain the given name, anywhere? ; (define (contains? anc target) ...) ;(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.) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; When traversing trees, many traditional (non-functional) books ; want to have a node-method do more than just call methods on its ; children; they want to reach down to its fields and do work using ; their info. The problem is, this requires ANOTHER check of whether ; the children are unknown-vs-Child -- the equivalent of a nested-cond. ; That doesn't smell right. ; ; It turns out, these problems can often be easily fixed by cleverly ; choosing a helper-function that takes in the node's info when recurring ; on its fields. ; Here are two examples: ; any-time-travelers? : anc-tree -> boolean ; (anybody born before their parents?)(*) ; (define (any-time-travelers? anc) (any-time-travelers-before-year? anc +inf.0)) ; any-time-travelers-before-year? : anc-tree, int -> boolean ; Are there either: somebody in the tree with a yob before their parent's, ; OR the root's yob is later than `last-year` ; (define (any-time-travelers-before-year? anc last-year) (cond [(unknown? anc) false] [(child? anc) ; We can't compare our yob with (child-yob (child-ma anc)), ; because ma and pa might each be Unknown. ; rather than add two more sub-cases here, we'll pass our yob ; to each of the sub-calls. (or (> (child-yob anc) last-year) (any-time-travelers-before-year? (child-ma anc) (child-yob anc)) (any-time-travelers-before-year? (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) ; entitle : AncTree -> AncTree ; Add "Mr." in front of each father's name, and "Ms." to each mother's, ; ... and "Baby" in front of the root's name. ; (Cf. walking an html tree and making some transform.) ; ; (define (entitle anc) (entitle-help anc "Baby")) (define (entitle-help anc title-for-root) (cond [(unknown? anc) 'unknown] [(child? anc) ; We can't know if we are part of somebody else's 'ma' field ; or their 'pa' field. Rather than try to add back-pointers ; to the tree, the caller can pass one thing to its pa's ; and a different thing to its ma's: (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" 1955 'brown (make-child "Ms. Mona" 1929 'brown 'unknown 'unknown) (make-child "Mr. Abe" 1920 'blue 'unknown 'unknown))) ; challenge: write 'any-duplicates', which returns ; whether there are two childs with the same name, ; where one is an ancestor of another. ; (But a 'Kris' on the mother's side and a 'Kris' on the father's ; doesn't count.) #| /** How would we write this same data structure (and programs) in Java? * * Many standard texts use a single class Child; they represent * Unkowns with `null`, and they don't use the name `AncTree` because * they just thing "Child-or-null". * * This has several problems: * - you can't call methods on your empty-data. * - It's easy to be unclear about what parameters/fields/local-vars * are AncTrees and which are Childs -- because they're both just * being declared as type Child. (Using annotations `@nonnull` * and `@nullable` help ease this concern.) * - you have lots of checks for `null`, and code for empty-trees * and non-empty trees is all inside class Child * ... Moral: If you're checking * for null or using `instanceof`, you're not really being O.O. * * THE SOLUTION: "the composite pattern" is how to implement * union-types in O.O. We'll have `Unknown`, `Child`, and `AncTree` * all be actual Java classes (just like we wrote in racket-comments). * We'll have Unknown and Child each extend AncTree (to capture "is a"); * we'll make AncTree abstract (to capture "...is exactly one of these sub-types"). */ 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; } 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: " + "??" ); } /** @Override */ public String toString( /* Child this */ ) { return "new Child" + "( " + "\"" + this.name.toString() "\"" + ", " + this.yob + ", " + "\"" + this.eye.toString() + "\"" + ", " + this.ma.toString() + ", " + this.pa.toString() + " )"; } } |# ; 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,