In this assignment you will learn the basics of ocaml by writing a lot of simple functions.
Read chapters 1 to 6 in the textbook. This is a fair amount of reading, but once it's done you'll understand the most basic parts of the ocaml language. Consider this to be the main part of your homework for week 1.
For this week, you will be solving a number of simple problems by writing
a bunch of simple functions in a file called warmups.ml.
Write these functions in a pure functional style only: no assignment
statements, no explicit loops, and no arrays!
Here are the problems you have to solve:
Write a function sqrt that takes a tolerance
tol and a floating-point number x and computes the
square root of that number to within the tolerance specified. The function
should look like this:
let sqrt tol x = (* your code here *)
and should have the type signature:
val sqrt : float -> float -> float = <fun>
Don't use a library function to compute square roots. Instead, use this
algorithm: for an input x and a candidate square root
y, compute a better approximation by:
y(next) = average(y, x/y)
This is not ocaml notation, of course. Repeat this until the
approximation squared is close enough to x, with "close enough"
specified by the first argument. Note that the function to compute absolute
values of floating-point values is called abs_float. Use helper
functions inside your sqrt function where appropriate; don't
pollute the global namespace with helper functions.
Write a specialized version of the previous function called
sqrt2 which will compute square roots to a tolerance of 0.00001.
Use the previous function to define this function. Don't refer to the input
variable x in your function definition (yes, it's possible).
This is a one-liner.
Write a simply-recursive (not tail recursive) function to compute
factorials (i.e. factorial 10 = 10 * 9 * 8 * ... * 2 * 1). Use an
if/then/else statement in the function. Call this function
factorial1. NOTE: if you don't know what "simply
recursive" or "tail recursive" functions are, then you need to find out
before you write this function. Ask the instructor, or do a web search
(Wikipedia has a nice article on tail recursion here). Have the
factorial function handle all numbers from 0 onwards (you don't have to check
for less than zero).
Rewrite the previous function using pattern matching instead of
if/then/else. Call this function
factorial2.
Write a new factorial function using pattern matching which is tail-recursive (i.e. it doesn't cause the stack to grow and there are no pending operations). You will need an internal helper function.
Write a function to compute fibonacci numbers (in the sequence 0, 1,
1, 2, 3, 5, ... where each number is the sum of the previous two numbers on
the list). Use pattern matching but no if/then/else statements.
Use a tail recursive solution to make sure the function doesn't take
exponential time. Call your function fibonacci. Test it by
computing the 44th fibonacci number. What happens when you try to compute
larger fibonacci numbers? Why? Indicate the answer in a comment in your
code.
Write a tail-recursive function called rev which takes a
list as an argument and returns a new list which contains the same elements
as those of the original list, but in reverse order. Include the type
signature of this function in a comment.
Write a simply-recursive function called map that takes
two arguments (a function and a list) and returns a new list consisting of
the function applied to each member of the original list. Write the type
signature of the function in a comment in your code.
Write another mapping function called map2 which is
identical to map except that it is tail-recursive. You may find
your rev function to be useful.
Write a function called range which takes two integers
a and b as arguments and returns a list of all the
integers in the range [a, b] (including a and
b). This is also a one-liner.
Use your map and sqrt functions to compute a
value called roots which is a list of the square roots of the
numbers 1 through 20 (expressed as floats). You will need the built-in
function float_of_int which converts integers to floats. You
can also do this in one line.
The file warmups.ml.
None this week. Instead just use the top-level ocaml interpreter. While in the interpreter type
# #use "warmups.ml";;
to compile your code (the first "#" is the ocaml prompt). Ocaml will also print out the type signatures of your functions, which you may find useful. Once this is done you can test your functions. In later labs I'll be supplying code which will test your functions non-interactively.
Note that your code must not generate any compiler warnings.
The ocaml manual. This is especially useful when looking for library functions.
Introduction to Objective Caml by Jason Hickey, chapters 1-6.
The Wikipedia article on tail recursion