Programming in SML I (Jan 13,14,16)

1. Why SML ? Basic values and operators
2. Tuples and Records
3. Lists

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


5.1) A time of day can be represented as a triple (hours, minute, f) where f is either AM or PM, or
as a record. Declare an SML function to test whether one time of day comes before another. For
example, (11,59,"AM") comes before (1,15,"PM"). Make solutions with triples as well as with
records. Declare the functions in infix notation and use patterns to build readable declarations.

5.2) The set of complex numbers is the set of pairs of real numbers. Complex numbers behave
almost like real numbers if addition and multiplication are defined by
(a,b) + (c,d) = (a+c, b+d)
(a,b)  * (c,d) = (ac -bd, bc + ad)

a) Declare infix SML functions ++ and ** for addition and multiplication of complex numbers
b) The inverse of (a,b) wrt addition i.e -(a,b) is (-a, -b) and the inverse of (a,b) wrt to
multiplication i.e 1/(a,b), is (a / (a*a + b*b), -b/(a*a + b*b)) provided a and b are both not zero.
Declare infix SML functions of subtraction and division of complex numbers.
c) Use let-expressions in the declaration of the division of complex numbers in order to avoid
repeated evaluation of identical sub-expressions.
d) Declare a function to give a string representation of a complex number in standard
mathematical notation i.e (a,b) is written as "(a + bj)" where j is the sq.root of -1.
6.1) Declare an SML function rmodd removing the odd-numbered elements from a list:

rmod[x1,x2,x3,x4,....] = [x2, x4, ... ]

6.2) Declare an SML function nubmer(x,ys) to find the number of times x occurs in the list ys.

6.3) Declare an SML function split such that:

split [x1,x2,x3,x4,.....xn] = ([x1,x3,....], [x2, x4,....])


6.3) A string is called a palindrome if it is identical with the reversed string instance
"ole elo" is a palindrome, while "ol elo" is not. Write a function determining whether
a stirng is a palindrome.

6.4) Declare a function sum (p,xs) where p is a predicate of type int->bool and xs is a list
of integers. The value of sum(p,xs) is the sum of the elements in xs satisfying the predicate
p. Test the function on different predicates (e.g p(x) = x > 0).