Practice Exercises On Lists And Structures

Practice exercises on lists and structures

To check your comprehension

Implement the following functions:

  1. (sum lon) returns the sum of all the numbers in the list of numbers lon
  2. (double lon) returns a list each of whose elements is twice the corresponding element in the list of numbers lon
  3. (lookup v lolsn) return the value associated with symbol v in list of (symbol, number) lists lolsn. In other words, scan lolsn until you find a sublist whose first element is v, and return its second element.

Each one can be written straightforwardly by recursion on the structure of a list. That means:

To prepare for recitation

Implement an evaluator for mathematical expressions. These expressions may take the following form:

Thus the evaluator should take the form of a function (mathval expr lolsn) where expr is any expression and lolsn is a dictionary that says what the values are for symbols.

You have to think carefully, but this function can also be written straightforwardly by recursion on the natural structure. You test which kind of expression you have, and evaluate it as appropriate. If the expression is composed of smaller subexpressions, then the evaluation will involve recursive calls to mathval for those smaller subexpressions.

You can use lookup of course! You will need it.

A challenge problem

You can use a list of numbers to represent a polynomial. The numbers in the lists represent the coefficients in increasing order. The variable of the polynomial is always assumed to be a fixed variable x. For example, the list (3 1 4 2) corresponds to the polynomial 3x0 + 1x1 + 4x2 + 2x3 or, more simply, 3 + x + 4x2 + 2x3. A bit of notation helps here: if lon is a list of numbers, then (vp lon) names its value as a polynomial. So (vp (3 1 4 2)) = 3 + x + 4x2 + 2x3.

The reason to think of the coefficients in increasing order is the following fact. Let lon have the form (n ron) with first coefficient n and remaining coefficients determined by the list ron. Then we have (vp lon) = n + x(vp ron). For example, (3 1 4 2) has head 3 and rest (1 4 2), so we're saying (vp (3 1 4 2)) = 3 + x(vp (1 4 2)) = 3 + x (1 + 4x + 2x2). See?

Write a function (eval-poly lon c) which calculates the value of the polynomial lon when x=c. You can take advantage of the fact from the previous paragraph. You should write the function recursively on the structure of the list, as always. That means handling the case where lon is empty. That's easy. And it means handling the case where lon takes the form (n ron). That's no problem either, if you understand the fact from the previous paragraph and recognize that the value of a polynomial is obtained by replacing x by c throughout.

Example instances:

Now write a function (add-poly p1 p2) which takes two polynomials p1 and p2 and returns their sum as a polynomial. For example:

Finally, write a function (diff-poly p) which takes the derivative of a polynomial p with respect to x. Recall that the derivative of cxn is ncxn-1. You might therefore be tempted to write diff-poly in such a way as to do this calculation directly. You can do that, but it involves putting together an auxiliary function - something that we haven't really delved into yet.

Another approach is to take advantage of the decomposition of polynomials and the sum and product rules for the derivative. Remember we are starting from the fact that (vp lon) = n + x(vp ron). Take the derivative of both sides with respect to x! d/dx(vp lon) = d/dx(n + x(vp ron)). Simplifying by the sum rule and the fact that n is constant, we get d/dx(vp lon) = d/dx(x(vp ron)). Now using the product rule and simplifying we get d/dx(vp lon) = (vp ron)+x d/dx(vp ron). That's enough to write diff-poly by direct recursion!