CSE 413 Au12 Assignment 2 - More Racket Programming

Due: Online via the Catalyst Dropbox by 11 pm, Thursday, Oct. 11, 2012.

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 atoms (names), you can either precede them with a quote (as printed by the current version of Racket) or just give the value, i.e., we will accept either (a b) or '(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. You should save your function definitions in a single file named hw2.rkt.

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 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 tree-like 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 prevent them from being evaluated to things like #<procedure:+>.
Write functions that traverse expression trees using inorder, preorder, and postorder traversals and return a list of the items 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 higher order function f to the value in the leaf node, e.g., each node v is replaced by (f v).

What to Hand In

Turn in a file containing your answers to the questions from Part I, your hw2.rkt source file for parts II and III, and a transcript file demonstrating the evaluation and results of your functions.

For the problems in part I please turn in a PDF file named hw1.pdf with your answers. This can be a scanned handwritten document if that is convenient, as long as it is clear and legible when printed and does not exceed roughly 2 or 3MB in size..

For parts II and III, turn in the hw2.rkt source file and 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... .