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));