Standard ML Programming/Solutions

Values and Functions

Problem: Indicate the identifiers, keywords, and special constants in the following piece of code. What is the value of the second a?

 val a = 5
 val b = 9
 val a = 2*a+b;

The identifiers are a, b, *, and +. The keywords are val, =, and ;. The special constants are 5, 9, and 2. The value of the second a is 19.

Problem: Construct a tuple with 4 positions and 3 components.

 (1,1,2,3)

is a simple one but this one is also valid

 (1,false,(3,2),1)

Problem: What is the type of t?

 fun f (a:int) = 2
 val t = (true,f,f 1);

Well the answer is

 bool * (int -> int) * int

Problem: Write a function that returns the value 2 for the arguments 0, 1 and 2 and returns 3 for all other arguments.

fun example(0) = 2
  | example(1) = 2
  | example(2) = 2
  | example(_) = 3;

or

fun example(x:int) = if (x>2) then 3 else if (x<0) then 3 else 2;

Problem: Write a function that returns -1 for all negative and +1 for all positive arguments and 0 for the argument 0.

fun example(x:int) = if (x=0) then 0 else if (x<0) then ~1 else 1;

One might try to use pattern matching like in the example above but "~" is an operator and thus can not be used in an argument pattern.

Problem: Create a function min(a:int,b:int) that returns the smaller one of its 2 arguments. Do the separation of the argument values in 3 different ways. Using a cartesian argument-pattern, using a projection and using a local declaration.

Using a cartesian argument-pattern

fun min(a,b) = if (a<b) then a else b;

Using a projection. Here we have to note the argument type as a 2-tuple of int*int. The value t will hold the whole tuple and thus for comparation it must be split up again.

fun min(t:int*int) = if (#1t < #2t) then #1t else #2t;

Using a local declaration.

fun min(t:int*int) = let val (a,b)=t in if (a<b) then a else b end;

Recursion

Problem: Create a function power9(x) that calculates the 9th power of x. Preferably using as few multiplications as possible.

The straight forward way to do this is could be:

fun power9(x) = x*x*x*x*x*x*x*x*x;

But thats no clever way and it also uses lots of multiplication. We could use local declarations inside the function to shorten the code and make it more readable.

 fun power9(x) = 
 let
   val a=x*x 
   val b=a*a 
 in 
   b*b*x 
 end;

or we could use helper-functions to calculate the partial products.

fun power2(x) = x*x;
fun power4(x) = power2(x)*power2(x);
fun power9(x) = power4(x)*power4(x)*x;

But that still isnt really smart. We would have to write lots of code for a function like power66(). The following code uses recursive function calls to calculate the n-th power of x.

fun power(x,n) = if (n=0) then 1 else power(x,n-1)*x;

which could be rewritten as

fun power(x,0) = 1
  | power(x,n) = power(x,n-1)*x;

Problem: Calculate the greatest common denominator from 2 positive integer arguments.

Using euclids algorithm we construct the recursive function

fun gcd(a,0) = a
  | gcd(a,b) = gcd(b,a-b*(a div b));

Problem: Calculate mul(n,z)=n*z without using the * operator for $n\in \mathbb {N}$ and $z\in \mathbb {Z}$

fun mul(n:int, z:int) = if (n=1) then z else z + mul(n-1,z);

fun h(a:int, n:int, z:int) = if (n=1) then z + a else h(a+z,n-1,z);
fun mul(n:int, z:int) = h(0,n,z);

Problem: Calculate power2(n) by only using addition and resursion. (hint: it is possible to rewrite the square function as a summation of natural numbers.)

The sum to be calculated is $power2(n)=\sum _{k=n}^{1}2*n-1$ which is the sum on the n first odd Elements of $\mathbb {N}$. Or on other words $power2(n)=1+3+\dots +2*n-1$.

fun power2(1) = 1
  | power2(n) = n+n-1 + power2(n-1);