CSE 413 21sp Assignment 2 - More Racket

Tuesday, April 13, by 11 p.m. You should use Gradescope to submit your assignment in two parts, corresponding to the written and programming parts below. Details are given in the "What to hand in" section at the bottom of the assignment.

All of these problems must be done without using side effects (i.e. redefining variables or using set!) and by using recursion instead of iteration constructs like do. Be sure to test your functions on various cases, including empty lists, simple lists with no sublists, complex lists, etc.

Some of the problems can be answered by just typing expressions into a Racket interpreter and transcribing the results. Feel free to use DrRacket to check your results, but, even though you might get the points, you won't learn what you need if you don't actually do the exercise.

For results that are lists or symbols (names), you shold precede them with a quote (as printed by Racket), i.e., you should write '(a b) for the result of (list 'a 'b).

Your code should include your name and other identifying information as comments.

Part I. Written (paper) problems

1. Suppose we enter the following definitions at the top-level of a Racket environment:

(define x 5)
(define y 7)
(define z 11)

What are the results when you evaluate the following expressions starting with just the above definitions?

(let ((x 0) (z (* x z))) (+ x y z))
(let ((x 2) (y (- x 4)) (z (* y 2))) (+ x y z))
(let* ((x 2) (y (- x 4)) (z (* y 2))) (+ x y z))

2. Consider the following definitions:

(define make-thing

(lambda (thing f)

      (lambda (x)

         (* thing (f x)))))



(define double

   (lambda (x) (+ x x))) 

        

(define mystery	(make-thing 3 double))

(a) Describe the result of evaluating (make-thing 3 double). What is it? (Your answer should be something like "the number 17", or "a function that adds 1 to its argument", or "a function that takes another function as an argument and ...".) If it is a function, describe the values bound in the closure as well as the code (expression) that is part of the function value.

(b) What is the value of (mystery 5)? Explain how you arrived at your answer. (For full credit, your answer should explain what happens when (mystery 5) is evaluated, not just report an answer that you got when you used DrRacket to evaluate these expressions.)

Part II. Tail Recursion & Higher Order Functions

Write and test Racket functions to solve the following problems. In some cases you may find it useful to write additional helper functions besides just the functions requested. You should save your function definitions in a single file named hw2.rkt.

The beginning of your file must contain comments giving your name and UW netid. Then, following the line containing #lang racket, your file must contain the following separate line, written exactly as shown:

(provide (all-defined-out))

(This provides an interface needed for the grading software to execute your code, but is not something you need to worry about as long as it is written correctly.)

General hint: Take advantage of map and other higher-order functions when appropriate. Your solutions do not have to be tail-recursive unless the specific problem requires it.

Write two versions of a tail-recursive function that computes the length of a list. The functions should return the same results as the built-in function length. For example,
```
   (lengtht '(a b c)) => 3
   (lengtht '((a b) (c d e)) => 2
```
1. Write a first version, lengtht that is tail recursive and uses external (non-nested) auxiliary functions as needed
2. Write a second version, lengtht2 that uses no additional top-level functions. The function should still be tail-recursive, and can use any local bindings that you want.
Write a tail-recursive function to compute the value of a polynomial given a value and a list of coefficients. If coeff is a list of coefficients (a0 a1 a2 ... an), then (poly x coeff) should compute the value a0 + a1*x + a2*x² + ... + an*xⁿ. For full credit, the running time of your solution should be linear in the degree of the polynomial (i.e., O(n)).You may define additional top-level functions or not as you wish. You may assume that the list of coefficients contains at least one item.
Write a function called apply-all that, when given a list of functions and a number, will produce a list of the values of the functions when applied to the number. For example,
```
(apply-all (list sqrt square cube) 4) => (2 16 64)
```
(assuming that suitable sqrt, square, and cube functions have been previously defined, of course)
Given a predicate that tests a single item, such as positive?, we can construct an "all are" version of it for testing whether all elements of the list satisfy the predicate. Define a procedure all-are that does this; that is, it should be possible to use it in ways like the following:
```
   ((all-are positive?) '(1 2 3 4)) => #t
   ((all-are even?) '(2 4 5 6 8)) => #f
```

all-are

function

Part III. More Data Structures in Racket

In this part of the assignment, you will create some functions to manipulate expression trees, using functions similar to the binary tree functions from the previous assignment. Here are some basics about expression trees:

Consider an arithmetic expression, such as one we would write in Racket as (+ 1 (* 2 (- 3 5))). We can think of this as being a linear representation of a tree structure with numbers at the leaves and operator symbols at the interior nodes.

This structure is known as an expression tree. For this problem, you should assume that the tree is restricted as follows:

Operators in the tree are all binary (i.e., have two operands)
All of the leaves (operands) are numbers

Each node in the tree can be represented by a three-element list:

(left-operand operator right-operand)

Write and test Racket functions to solve the following problems. You should save all of your function definitions for this part of the assignment in your hw2.rkt source file.

General observation (hint): Binary trees have an elegant, recursive structure. Take advantage of this to structure your code.

Write functions to create new expression tree nodes and extract fields from them. The functions you should create are:
```
     (make-expr left-op operator right-op)   => (left-op operator right-op)
     (operator '(left-op operator right-op)) => operator
     (left-op '(left-op operator right-op))  => left-op
     (right-op '(left-op operator right-op)) => right-op
```
Notice that unlike in assignment 1, the leaf values are simple integers, not leaf nodes with null subtrees (e.g., 4 rather than(4 () ())). A few examples:
```
     (make-expr 4 '+ 5) => (4 + 5)
     (make-expr '(6 * 3) '+ '(5 - 2)) => ((6 * 3) + (5 - 2)) 
```
Quoting operators like + when appropriate will treat them as symbols and prevent them from being evaluated and returning the values they are bound to like <procedure:+>.

Write functions that traverse expression trees using inorder, preorder, and postorder traversals and return a list of the items (operators and values) encountered during the traversal in the order encountered. You should use the functions from question 1 to access the components of the tree.
```
     (preorder  expr-tree)
     (inorder   expr-tree)
     (postorder expr-tree)
```
Test your functions by creating a few trees using nested make-expr function calls and then using these as arguments to the traversal functions.

Write a function
```
(eval-tree expr-tree)
```
that evaluates an expression tree by traversing it and returning the value that it represents. You may assume that the only operators present in the tree are +, -, *, and /. You also can ignore the possibility of division by 0.

Write a higher-order function
```
(map-leaves f expr-tree)
```
that returns a copy of the given expression tree that is the same as the original tree except that each leaf node v is replaced by the result of applying the function f to the value in the leaf node, e.g., each node value v is replaced by (f v).

What to Hand In

Use Gradescope to submit your solutions to this assignment in two parts.

For the problems in part I please turn in a pdf file named hw2.pdf with your answers. This can be a scanned handwritten document if that is convenient, as long as it is clear and legible. Gradescope's web site has several instructional videos and help pages to outline the process, and this guide has specific information about scanning and uploading pdf files containing assignments.

Unreadable solutions cannot be graded--no blurry photos, poor contrast, or illegible handwriting, please.
Type-written solutions are encouraged but not required.
If possible, don't split the solution to a problem across a page break.

For parts II and III, turn in the hw2.rkt source file containing your Racket functions. Use comment lines (starting with ;;) to label your code so we can easily find the solutions to each problem. (But don't overdo it. Excess clutter is just bad unlabeled code.) Be sure that your file contains the (provide ...) line described at the beginning of part II.

Also submit a text file named hw2demo.rkt containing the transcript of a Racket session demonstrating the results produced by your functions for suitable test cases. This should contain enough to show that your functions work, but no more than necessary to do that. Part of your grade will be determined by the quality of the test cases you use for this. (Don't worry if there are some minor typos in the transcript - just make a comment (;; line) to indicate anything we should ignore.) To save the transcript of the DrRacket interactions window to a file, use File > Save Other... > Save Interactions as Text... .