Description
In this lab assignment, you will write three recursive OCaml functions that perform computations with lists. It’s primarily intended to introduce OCaml’s notation, which may be unfamiliar to many students.
1. Implementation.
Here are brief descriptions of the functions you must write, some examples of how they must work, and some hints about how to write them.
Your functions must use the OCaml’s if–then–else, let–in, and let–rec–in, as discussed in the lectures. They must also use the OCaml functions hd, tl, and :: (cons), again as discussed in the lectures. Your functions will be similar in design to those of other languages, such as Java and Python, although their notation will be different. Later in the course, we will discuss better ways to write functions like these, using OCaml’s pattern matching mechanism.
How Many. Your first function must be called howMany, and it must accept two arguments: e and l. The argument e may be any object. The argument l must be a list of objects with the same type as e. The call howMany e l must return how many times e appears as an element in l. The type of howMany must be 'a -> 'a list -> int. Here are some examples of how howMany must work, where the symbol ‘⇒’ means returns.
howMany 1 []
⇒
0 howMany 1 [1]
⇒
1 howMany 2 [1 ; 2 ; 3]
⇒
1 howMany 5 [2 ; 4 ; 6]
⇒
0 howMany "c" ["c" ; "b" ; "c" ; "d"]
⇒
2 howMany "x" ["a" ; "b" ; "c" ; "d"]
⇒
0
Hints: write a recursion with one base case and two recursive cases. The base case detects when l is empty. The first recursive case detects when e is the first element of l. The second recursive case detects when e is not the first element of l.
Delete. Your second function must be called delete, and it must accept two arguments: e and l. Just as in howMany, e may be any object, and l must be a list of objects with the same type as e. The call delete e l must return a list like l, but without any e’s as elements. The type of delete must be 'a -> 'a list -> 'a list. Here are some examples of how delete must work.
delete 1 []
⇒
[] delete 1 [1]
⇒
[] delete 1 [1 ; 2 ; 3]
⇒
[2 ; 3] delete 4 [1 ; 2 ; 3]
⇒
[1 ; 2 ; 3] delete 1 [1 ; 2 ; 1 ; 3 ; 1 ; 4]
⇒
[2 ; 3 ; 4] delete "a" ["x" ; "a" ; "y" ; "a"]
⇒
["x" ; "y"]
Hints: This function should have a base case and two recursive cases. The base case detects when l is empty. The first recursive case detects when e is the first element of l. The second recursive case detects when e is not the first element of l, and it must use ::.
Mean. Your third function must be called mean, and it must accept one argument l, a list of one or more float numbers. The call mean l must return the arithmetic mean (average) of all the numbers in l. You may assume l will never be empty, so mean [] may be undefined. The type of mean must be float list -> float. Here are some examples of how mean must work.
mean [1.0]
⇒
1.0 mean [1.0 ; 2.0]
⇒
1.5 mean [1.0 ; 0.0 ; -1.0 ; 1.0]
⇒
0.25
Hints: The arithmetic operators for float’s have annoying names that end with dots: +., -., *., and /.. The usual operators =, <>, <, >, <=, and >= work for floats, but without the dots. Also, OCaml does not coerce int’s to float’s, so 0 is different from 0.0.
The best way to write mean is to use two ‘‘helper’’ functions, which might be called length and sum. The function length returns the number of elements in l. The function sum adds all the elements in l and returns their total. These helper functions might be defined inside mean, using two nested let–rec–in’s. They could also be defined as separate functions, outside mean.
2. Tests.
For this assignment, you will use OCaml’s read-evaluate-print-loop (REPL) to execute and test your functions. Here’s one way to do that. It assumes you’re running OCaml from something like a Linux or Unix shell.
-
Use a text editor to write code for your functions on a text file. The file’s name must end with the suffix .ml. Let’s assume your file is called dromedary.ml (a dromedary is a camel with one hump, but a Bactrian camel has two). Use a different name for your file. The first line of dromedary.ml must be open List, which loads the List module from OCaml’s library. This module defines the functions hd and tl, among other things.
-
The rest of dromedary.ml must contain definitions for the three functions described previously. Some can be defined with let, others with let–rec. Each definition must be terminated by ;;.
-
To test your functions, type the command ocaml to the shell. OCaml will print a brief message and respond with a prompt #. Type #use "dromedary.ml" ;;. (You must type another ‘#’ even though OCaml has printed one already.) OCaml will load the code from dromedary.ml and execute it to define your functions.
-
If there are syntax errors in your code, then OCaml will print error messages. If that happens, then exit OCaml by typing the single character control–D. Go back to step 1 and fix the errors.
-
If there are no syntax errors, then OCaml will print the following. It tells you what functions dromedary.ml defined, and what their types are.
val howMany : 'a -> 'a list -> int = <fun>
val delete : 'a -> 'a list -> 'a list = <fun>
val mean : float list -> float = <fun>You can now type some example calls to OCaml that test your functions. Each call must end with ;;. For example, you might type howMany 1 [] ;;. If your function call doesn’t work the way it should, then exit OCaml and go back to step 1, as before.
-
When you’re confident that your functions work, then run the tests for this assignment. They’re on the file tests1.ml, so you run them by typing #use "tests1.ml" ;; to OCaml. Each test has a function call, a comment that tells what the call must return if it’s correct, and a number of points. If your function returns the same object that appears in the comment, then you’ll receive the points. Your score for this assignment will be the total number of points you receive on all the tests.
You might have a fancy IDE (Integrated Development Environment) that does some of these things for you automatically. All IDE’s work differently, so they aren’t described here.
3. Deliverables.
Run the tests in the file tests1.ml. They are worth 30 points. Then submit the OCaml code for your functions, the tests, and the results of the tests, all in one file. Put the test results in a comment (∗ … ∗) at the end of your file. Your lab TA’s will tell you how and where to turn in your work. It must be submitted by 11:55 PM on Tuesday, September 21, 2021.
