Homework 1: ML Basics

Objectives
The purpose of this homework is to get you up to speed with ML. By now, you should be already familiar
with the SML environment. Feel free to use the course web page to find additional information and tutorials
if needed. Handin a single text file (.sml extension) with your answers. Do respect the name of the functions
to ease grading. If you need helper (auxiliary) functions, feel free to add them. Do comment your code.
1 Question 1
1. Write an ML function sum which, given an integer n computes the sum of the first n naturals. Namely,
it computes:
Xn
i=0
i
fun sum n = ...
2. Extent your sum function into a sumsq function. Given a natural n, sumsq computes the sum of the
squares of the first n naturals:
Xn
i=0
i
2
fun sumsq n = ...
3. Write an ML function sumOdd which, given a natural n computes the sum of the first n odd naturals.
For instance, sumOdd 4 = 1 + 3 + 5 + 7 (i.e., we have four terms).
fun sumOdd n = ...
4. Write an ML function fib that computes, from an integer input n, the n
th Fibonacci number (as
always, f ib(i) = f ib(i − 1) + f ib(i − 2), f ib(0) = 0, f ib(1) = 1).
fun fib n = ...
5. Write an ML function fibFast that computes, in linear time, from an integer input n, the n
th Fibonacci’s number.
fun fibFast n = ...
1
2 Question 2
Consider the Taylor expansion of the sin function
sin(x) ≈ x −
x
3
3! +
x
5
5! −
x
7
7! + · · ·
As you can see, it is also a sum of terms with a couple of twists. First, the signs alternate, second and the
terms for even numbers are missing. The formula in sigma notation is
sin(x) ≈
Xn
i=0
(−1)i
(2 · i + 1)!.x2·i+1
where the order−n summation contains the first n + 1 terms of the expansion. Write a linear time ML
function sinappx that, given a value n, computes in linear time in n, the Taylor expansion up to order n.
As you surely realized, computing (for instance) factorials from scratch for each term would not deliver the
desired complexity.
fun sinappx n x = ...
3 Question 3
Your task is to write a function that compute a definite integral, namely,
Z b
a
f(x)dx
where f is an arbitrary continuous unary function. Naturally, you should provide a numerical solution using
a simple method such as the trapezoidal method over a collection of boxes that sub-divide the integration
interval [a, b]. Formally, given f, a, b and n, subdivide the range [a, b] into n sub-intervals (of width b−a
n
) and
compute the integral as the sum of the surfaces of the trapezoid embedded in each sub-interval.
fun integrate f a b n = ...
4 Question 4
The variance of a list of reals [a1, a2, · · · , an] is the average of the squares minus the square of the average,
i.e.,
Pn
i=1 a
2
i
n
−
?Pn
i=1 ai
n
?2
Write the most elegant ML function variance you can that computes the variance. (Short and clear
is ideal). The function takes as input a list of integers. Remember that ML types all the expressions it
encounters and does not mix integers and reals. If you have an integer that you wish to convert to a real for
arithmetic purposes you can use the function fn real : int - real. Similarly, do recall that the types
of the two literals 0 and 0.0 are 0 : int while 0.0 : real.
Have fun!
2