Homework # 5
due Tuesday, March 2, 4:00 PM

Simple Programming

Solve Exercises 18-21 from Chapter 9. Your answers should be one-liners, and in particular, must not use recursion. Put your answers in the file oneline.sml.

The definition of foldl seems backwards to some people. Define a new function lfold such that lfold $f$ $c$ $[x_1,\ldots,x_n]$ is

$$f(\ldots f(f(c,x_1), x_2), \ldots, x_n)$$

In particular:

- lfold (op -) 0 [1,2,3,4];
val it = ~10 : int

Also put your answer in the file oneline.sml even though this function is a two-liner (and uses recursion).

Ring

In ``group theory'' (a branch of mathematics), a ring consists of two operations ``addition'' and ``multiplication'' as well as two constants ``zero'' and ``one.'' We can declare a ring type constructor:

type 'a ring = ('a * 'a -> 'a) * ('a * 'a -> 'a) * 'a * 'a;

Now we can declare a ring for integers and a ring for reals:

val intRing : int ring = (op +, op *, 0, 1);
val realRing : real ring = (op +, op *, 0.0, 1.0);

The polynomial routines written for Homework #4 can be generalized to work for any ring. Starting with your code (or the solution to Homework #4), write curried versions of the functions eval, pow and polyToString that work for any ring. Their types should be as follows:

eval : 'a ring -> 'a list -> 'a -> 'a
pow : int -> 'a ring -> 'a list -> 'a list
polyToString : 'a ring -> ('a -> string) -> 'a list -> string

Thus we can write:

- fun polyCube r = pow 3 r;
val polyCube = fn
  : ('a * 'a -> 'a) * ('a * 'a -> 'a) * 'a * 'a -> 'a list -> 'a list
- polyToString intRing Int.toString (polyCube intRing [1,2]);
val it = "8x^3 + 12x^2 + 6x + 1" : string
- val p = polyCube realRing [1.0,2.0];
val p = [1.0,6.0,12.0,8.0] : real list
- polyToString realRing Real.toString p;
val it = "8.0x^3 + 12.0x^2 + 6.0x + 1.0" : string
- val func = eval realRing p;
val func = fn : real -> real
- func 0.1;
val it = 1.728 : real

Optional Thought: For those of you interested in mathematics, it happens that polynomials form a ring too. What would the ring of integer polynomials look like? What would a polynomial of polynomials look like?

Paper

Do Exercises 2 and 3 on page 163.

Submitting Your Work

You submit your program work by putting it in the homework5 directory in your AFS class volume. You may do all your work in this directory, or you may wish to do your work in a different directory and copy things when correct into this directory. In any case, you will lose permission to write things in this directory after the deadline, which is 4:00pm on Tuesday, March 2nd. In other words, you must be done before lecture starts.

The homework5 directory should include the following:

• oneline.sml
• newpoly.sml

About this document