CSE 341 -- Programming Languages

Spring 2003

Department of Computer Science and Engineering, University of Washington

Steve Tanimoto (instructor)

Assignment 5

Version 0.8 of 2 May

Introduction to ML

Due date and time: Monday, May 12 2003 (at the beginning of class).

Turn in this assignment as hardcopy.

Title: Introduction to ML.

Purposes: Work briefly with a functional language that has (a) a uniquely powerful type system, and (b) more conventional syntax that Lisp's.

Instructions: Read the following sections of Andrew Cumming's online "Gentle Introducton to ML".
In Lesson One, "'Hello World' is our First Program". "Tutorial One concerns expressions and simple functions." "Self Test One: some multiple choice questions to try."
In Lesson Two, "Types, bindings, pattern matching and lists are all introduced." "Tutorial two." "Self Test Two."
In Lesson Three, "More on types, Currying and recursion." "Tutorial Three (simple recursion on integers)." "Self Test Three."

Programming Instructions

Each team of two people should produce solutions to each of the following two problems. The intent is for each person to do one of the problems. However, you may work as a partnership to get the programs working.

Polynomial Representation


A polynomial is a mathematical function of the form
          n       n-1
f(x) = a x + a   x    + ... + a .
        n     n-1              0

A root r of a polynomial f(x) satisfies f(r) = 0.

Suppose that polynomials are represented in ML as lists
of coefficients in reverse order...  [a , a , ..., a ]
                                       0   1        n

Then given a list of roots [r , r , ..., r    ]
                             0   1         n-1
find the ML representation of the polynomial f(x) that has
those roots.

Note that f(x) = (x - r ) (x - r ) ... (x - r   )
                       0        1            n-1
You should write whatever helper functions you need, including
one for polynomial multiplication.

Test your function on the following lists of roots:
[~2.0, 2.0], [1.0, 1.0, 1.0], [0.0, 1.0, 2.0, 3.0].

Rough integrals.

One way to approximate the integral of a given real-valued
function in an interval [a, b] is to break the interval into
n equal parts for some n > 0, and add up the areas of the
rectangles of width (b-a)/n and height f(x) where x is the
coordinate of the left corner of each rectangle.

Write an ML function roughIntegral that takes a function,
values a and b for the interval, and number n.  It should
return a real number giving the approximate integral computed
in this way.

Test your function on...
                               2
The function f(x) = sqrt (1 - x ) with a=0, b=1, n = 4;
The same function and interval, with n = 10;

The function f(x) = x, with a = 10, b = 20, n = 10;