CSCI 330: Tail Recursion with OCaml

Goals

Overview

You have been tasked with implementing several additional functions in OCaml. All of the programs require relatively little coding ranging from 2 to 10 lines. If any function requires more than that, you will need to rethink your solution.

  1. Download the handout file from Autolab
  2. Update each of the functions with your own solutions. As a reminder, you are expected to complete this individually.
  3. Test your program using the OCaml environment installed on the Linux Lab machines
  4. Submit your updated handout file to the “Lab 2” Autolab assignment.
  5. You may not use references, arrays, or loops. You may also not use any additional libraries.

Grading Note: Correctness is done through autolab, but there are some requirements for this assignment which require me to manually inspect your code. Make sure you meet all requirements – if you fail to follow the specifications, expect to lose points even if it yields the correct results

Function Descriptions

You are required to implement each of the following functions. They should bind only one symbol at the top level. DO NOT litter the global namespace with helper functions. NEST THEM

factorial1 (6 points)

A simple recursive function which computes factorial of a passed integer. Use if-then-else within this function. n must be non-negative. The structure will be manually inspected

Expected Output

factorial1 4;;

(* int = 24 *)

factorial2 (7 points)

factorial2 is like factorial1 except you should use pattern matching instead of if-then-else. The structure will be manually inspected

factorial3 (7 points)

This is a tail-recursive function which should compute factorial. NOTE: you will need an internal helper function. The structure will be manually inspected

fibonacci (15 points)

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 (no if-then-else statements). Use a tail recursive solution to make sure the function doesn’t take exponential time. The structure will be manually inspected. Call your function fibonacci. A call to fibonacci should return the n th number in the sequence where n is zero-based.

Test your function by computing the 44th fibonacci number. What happens when you try to compute larger numbers? Why? Indicate the answer in a comment in your code.

Expected Output

fibonacci 3;;

(* int = 2 *)

sqrt (15 points)

Write a function sqrt that takes a tolerance tol and a floating-point number x which 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:

next(y) = average(y, x / y)

This is not OCaml notation, of course. Repeat this process until the approximation squared is close enough to x, with “close enough” specified by the first argument (tol). Note that the function to compute absolute values of floating-point values is called abs_float.

sqrt2 (5 points)

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. This is a one-liner.

map (10 points)

Write a simply-recursive function (not tail recursive) 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. There is a built-in map function. You may not use it. The structure will be manually inspected

map2 (10 points)

Write another mapping function called map2 which is identical to map except that it is tail-recursive. You may find your reverseList function from the first lab to be useful (make sure this function is also tail recursive). The structure will be manually inspected

range (5 points)

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). If b is less than a, an empty list should be returned.

Expected Output

range 2 5;;

(* int list = [2; 3; 4; 5] *)

roots (5 points)

NOTE: This is not a function, but is instead a value

Use your map, sqrt2, and range functions to compute a value called roots which is a list of the square roots of the numbers 1 through 20 to a tolerance of 0.00001 (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.

Submission

Submit tail.ml as the “Tail Recursion” assignment through Autolab

Grading

100 points total

Attribution

This assignment was adapted from CalTech’s CSE 11 course.