Homework 10

Please read chapter 20 Incremental Refinement, and chapter 21 Refining Interpreters in the textbook.

Be sure to include type, purpose, definition and tests for all functions.

Include the following at the top of your homework:

#lang typed/racket

(require "../include/uchicago151.rkt")
(require typed/test-engine/racket-tests)

And include (test) at the bottom of your homework.

You will also need the following batch of data structures:

(define-struct None ())
(define-struct Person
  ([name : String]
   [yob : Integer]
   [father : FT]
   [mother : FT]))
(define-type FT (U None Person))

Problem 1

Write the following functions using the FT structure.

• average-yob which will compute the average year of birth
• names which will make a list of names in the tree

Problem 2

Add the following tree structures to your code:

(define-struct Empty ())
(define-struct Num-Node
  ([n : Number]
   [l : Num-Tree]
   [r : Num-Tree]))
(define-type Num-Tree (U Empty Num-Node))

(define-struct Str-Node
  ([n : String]
   [l : Str-Tree]
   [r : Str-Tree]))
(define-type Str-Tree (U Empty Str-Node))

(define-struct (Node A)
  ([n : A]
   [l : (Tree A)]
   [r : (Tree A)]))
(define-type (Tree A) (U Empty (Node A)))

To make sure you understand the structures, I suggest first making sure that you can draw the following tree on paper:

(Num-Node 4 (Num-Node 2 (Empty) (Empty))
          (Num-Node 8 (Num-Node 7 (Num-Node 6 (Empty) (Empty)) (Empty)) (Empty)))

Use the above structures to write the following five functions:

• double-nums : Num-Tree -> Num-Tree will double all the numbers in a tree. For example, double-nums applied to the above tree should result in the tree:

  (Num-Node 8 (Num-Node 4 (Empty) (Empty))
            (Num-Node 16 (Num-Node 14 (Num-Node 12 (Empty) (Empty)) (Empty)) (Empty)))
  

• upper-case : Str-Tree -> Str-Tree will make all of the strings in a tree uppercase using the string-upcase function.
• to-strings : Num-Tree -> Str-Tree will make a tree of strings of the numbers using the number->string function.
• tree-map : (All (A B) (A -> B) (Tree A) -> (Tree B)) which will take a function and a polymorphic tree as input and apply the function to each item in the tree. You should be able to use your map function to create the previous three functions on polymorphic trees
• tree-fold : (All (A B) (A B -> B) B (Tree A) -> B which will take three inputs: a function, an initial input value, and a polymorphic tree. Your tree-fold function should be similar to the list foldl or foldr function: it should apply the function sequentially to each item in the tree and the previous result. If you have trouble writing this, first try writing these as practice:
  • add-nums : Num-Tree -> Number
  • mult-nums : Num-Tree -> Number
  • append-strings : Str-Tree -> Number Note that there are many correct solutions to this one that will have the strings appended in different orders.

Problem 3

In this part, you will write your own higher-order functions, similar to the built-in map, foldr, or filter functions. To implement them, write recursive functions. You may use the built-in map, filter, or folding functions, but are not required to do so. After you implement each, you will then use them to perform a task that cannot be easily accomplished with the built-in ones.

• (: condmap : All (A) (A -> Boolean) (A -> A) (Listof A) -> (Listof A)) which maps over a list, but only maps a particular value to a new value using the second function if the result of the first function, given the original value, is true. If that function returns false, the original value continues through to the new list unmodified.
• (: find-replace : All (A) (A A -> Boolean) A A (Listof A) -> (Listof A)) which, given an equality function, a "find" value and next a "replace" value, replaces all occurrences of the find value in the list with the replace value, leaving the rest of the list unmodified. For credit, use condmap to build your solution.

---

• (: foldrpair : All (A B C) (A B C -> C) C (Listof A) (Listof B) -> C) which takes in two lists, and a folding function that takes in one value from each as well as the partial folding result, and generates a new partial folding result. The first element from each list will be provided to the first call of the folding function, then the second element of each list, and so on. Raise an error if the lists are of different lengths.
• (: weighted-mean : (Listof Real) (Listof Real) -> Real) which uses foldrpair to calculate the weighted arithmetic mean of the specified data, where one of the two lists represents values and the other, weights. You may assume that the weights sum to one; in other words, you need only take the dot product of the two lists, not divide at the end.

---

• (: index-map : All (A B) (Integer A -> B) (Listof A) -> (Listof B))which maps over all elements of a list, but calls the map function with both the value of the present element and its index (location) within the list (starting at zero for the first element).
• (: replace-at : All (A) Integer A (Listof A) -> (Listof A)) which, using index-map, replaces the element in the list at the given index with the specified new value, leaving the rest of the list as-is; the function has no effect, and no error, if the index does not represent a valid index in the list.

Practice

Please be sure to practice with lambda and match. You are seldom required to use them, but they will be on the quiz. Also be sure to practice with map, filter, fold, and build-list: they will also be on the quiz.

Submit your work in your repository in hw10/hw10.rkt by noon Wednesday, July 12.