CS330 Spring 2004 Lecture 4

George Tzanetakis

Slides 

This lecture will not contain any slides as it consists mainly of
programming examples in sml.

SML code

Code in text format

Supporting web resources 

A gentle introduction to ML (Andrew Cumming)

Bob Harper's Programming in SML


Suggested exercises

4.1) Which of the following functions definitions require type constraints ?

fun double(n) = 2 *n;
fun g k = ~k * k;

4.2)  The following figure gives the first part of Pascal's triangle:

           1
        1    1
     1    2    1
  1    3    3   1
1  4     6    4   1
........................

The entries of the triangle are called binomial coefficients. The kth binomial
coefficient of the nth row is binomial(n,k) for n>=0 and   0<=k<=n. The first
and last binomial coefficients, i.e binomial(n,0) and binomial(n,n) are both 1.
A binomial coefficient inside a row is the sum of the two binomial coefficients
immediately above it.

Declare an SML function binomial:int*int->int to compute binomial
coefficients.

4.3) Consider the declaration:

fun f(0,y) = y
    |  f(x,y) = f(x-1, x*y);

a) Determine the type of f
b) For which arguments does the evaluation of f terminate
c) Write the evaluation steps for f(2,3)
d) What is the mathematical meaning of f(x,y) ?


4.4) Suppose we execute the following sequence of definitions:

val a = 2;
fun f(b) = a *b;
val b = 3;
val a = 3;
fun g(a) = a + b;


Give the value of the following expressions (without using the SML compiler
and compare them with the output of the SML compiler afterwards)

a) f(4)
b) f(4) + b
c) g(5)
d) g(5) + a
e) f(g(6));
f) g(f(7));