Homework # 5
due Thursday, April 5, 2:00 PM

Simple Programming

Solve the following one line programming problems: Exercises 10, 18, 19 of Chapter 9. Your answers should not use recursion, but should instead use a ``fold'' function to do the work.

10.

Write a function dupList of type 'a list -> 'a list whose output list is the same as the input list, but with each element of the input list repeated twice in a row. For example if the input list is [1,3,2], the output list should be [1,1,3,3,2,2]. If the input list is [], the output list should also be [].

18.

Write a function min of type int list -> int that takes a list of integers and returns the smallest one; it may crash if passed the empty list.

19.

Write a function member of type ''a * ''a list -> bool so that member(e,L) is true if and only if e is an element of list L.

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 4 on page 163:

2.

Investigate and report on the block constructs name let, let* and letrec in the language Scheme. Explain the scoping differences fully.

4.

Consider the following Java code (from the JLS):

class Reuse {
  Reuse Reuse(Reuse Reuse) {
    Reuse:
      for (;;) {
        if (Reuse.Reuse(Reuse) == Reuse)
          break Reuse;
      }
      return Reuse;
  }
}

Copy it onto paper and annotate as follows:

1. For each occurrence of the identifier Reuse that is a definition, describe what binding for Reuse is established.
2. For each occurrence of the identifier that is not a definition, show which definition is being used to bind it.

Submitting Your Work

Turn in your homework at the start of lecture, April 5, 2007.

About this document