# Assignment 6: Mutation, Streams This is a **pair or solo Gradescope assignment**—you will submit 2 OCaml files (`a6.ml` and `a6test.ml`) and a README on Gradescope. :::info Recall that assignments, if completed as a pair, must be completed and submitted **together** rather than dividing work. See the syllabus for more. ::: In this assignment, you will define 8 OCaml functions (potentially with additional helper functions). Except where otherwise noted, you may use functions in OCaml’s library. The sample solution is 90 lines including the provided code. :::warning For this assignment, you may reference any OCaml language documentation, the [free online OCaml textbook](https://cs3110.github.io/textbook/cover.html), and the class notes. You should not use any other resources without checking with me first! ::: Parts 1 & 2 (problems 1-4) cover material that is in scope for Quiz 2, I suggest completing them by Sunday. Part 3 covers material (Streams) that is not in scope until quiz 3. --- # **Change Log** I will avoid making changes to the assignment after it is posted, but any necessary changes will be added here: - [3/26] added type summary at the end - [3/31] clarify stream stencil code --- # Setup ### Attribution This assignment is adapted from a [CS341](https://sites.google.com/cs.washington.edu/cse341autumn2024) assignment from the University of Washington. ### Stencil code I've provided following [starter code](https://drive.google.com/file/d/1RcHh8Qxlnm4MhJr2j0Waqr03XQDyv5N3/view?usp=sharing) (requires Wellesley access). Files you should edit are in green: :::success - `a6.ml`, where you should implement the required functions and any helper functions you'd like. - `a6test.ml`, where you should write tests for each function. ::: :::warning - `a6.mli`, the interface (function type definitions) you should complete. Read, but do not edit, this file. - `a6types.ml`, provided type defintions. Read, but do not edit, this file. - `dune`, `dune-project` setup files so that you can test the project using `dune test`. Don't worry about reading or editing these, unless you are curious. ::: ### Before you submit Make sure that run `dune test` without error. Do not modify `a6types.ml` and do not turn it in. Make sure you are able to see results from the Gradescope autograder. # **Problems** :::success For each function, you should write your own tests in `a6test.ml`. If you are unsure about the expected result for specific inputs, please post a question on Zulip. ::: # Part 1: Warmup: more functional OCaml ## **Problem 1** :::success Write a function `sequence` that takes 3 `int` arguments called `spacing`, `low`, and `high`. It should return an `int list` of numbers from `low` to `high` (possibly including `high`) separated by `spacing` in sorted order. Assume `spacing` is positive. ::: See the provided tests for a few examples. The sample solution is 5 lines. ## **Problem 2** :::success Write a function `list_nth_mod` that takes a list `xs` and an `int` called `n`. - If `n` is negative, you should raise a `NegativeInput` exception. - If the list is empty, you should raise an `EmptyList` exception. - Otherwise, return the ith element of the list where we count from zero and `i` is the remainder produced when dividing `n` by the length of `xs`. ::: The sample solution is 6 lines and uses two functions from the standard library `List` module. ## **Problem 3** :::success Write a function `array_assoc` of type: ```ocaml 'a -> ('a * 'b) option array -> 'b option ``` The function takes a key `k` and an array `a`. It should behave like `List.assoc_opt` ([documentation](https://ocaml.org/manual/5.3/api/List.html)) except: 1. It processes arrays instead of lists. 2. It allows the elements of the array to be `None`, in which case it skips them. ::: Your function should scan the array from left to right looking for a non-`None` pair whose first component is equal to `k`. Return `None` if no such pair exists. Return `Some v` where `v` is the second component of the first matching pair if it exists. The sample solution is 12 lines and uses a local recursive helper function. # Part 2: Mutation A [_cache_](https://en.wikipedia.org/wiki/Cache_(computing)) is a useful concept across many areas of computer systems. The core idea of a cache is to keep around recently (or frequently) accessed results in an easier-to-access manner. When caches are used to save results of earlier computation, this is also called [_memoization_](https://en.wikipedia.org/wiki/Memoization#:~:text=In%20computing%2C%20memoization%20or%20memoisation,the%20same%20inputs%20occur%20again.). In the next problem, you'll implement a simple cache for an associative array using references and a mutable array. ## **Problem 4** :::success Write a function `caching_assoc` of type: ```ocaml ('a * 'b) list -> int -> 'a -> 'b option ``` The function takes a list `xs` and an int `n` (you can assume `n` positive) and returns a function that takes one argument `k` and returns the same thing that `List.assoc_opt k xs` would return. However, you should use an `n`-element cache of recent results to possibly make this function faster, rather than directly calling `List.assoc_opt` in all cases. ::: Your function will probably only be faster if `xs` is long and the same few elements are accessed frequently. The cache should be an array of length `n` that is allocated as soon as `caching_assoc` is partially applied to its first argument, and then used-and-possibly-mutated each time the returned function is called. The cache starts empty (all elements `None`). When the function returned by `caching_assoc` is called, it first checks the cache for the answer (using `array_assoc`). If it is not there, it uses `List.assoc_opt` on `xs` to get the answer, and if the answer is not `None`, then it adds the answer to the cache. The cache slots should be used in a round-robin fashion (similar to a [circular buffer](https://en.wikipedia.org/wiki/Circular_buffer) or queue): the first time a pair is added to the cache, it is put in index 0, then the next pair in index 1, and so on up to index n-1 and then back to index 0 (replacing the pair already there), then index 1, etc. The sample solution is under 15 lines. :::info *Hint*: In addition to the array holding the cache, you will want a second mutable value to keep track of which cache index will be replaced next. ::: :::info *Hint*: To test your cache, it might be useful to add print expressions so that you know when you are using the cache and when you are not. Remove these print expressions before you submit. Alternatively, you can write a version of the function that returns a boolean for whether the result was retrieved from the cache, but again, remove this before submission. ::: --- # Part 3: Streams :::info Note for some of these problems, the stencil code starts with: ```ocaml Stream (fun () -> failwith "...not implemented") ``` This is just so that the function has the correct type for the autograder to build, even if you do not complete that problem. You can replace that entire line with your solution, your answer does not need to start with `Stream`. ::: ## **Problem 5** :::success Write a function `stream_first_k_such_that` that takes arguments - `p : ‘a -> bool` - `k : int` - `t : ‘a stream` It returns a **list** (not a stream) holding the first `k` values produced by `s` on which `f` returns `true`, in the same order as they were produced by `s`. Assume `k` is nonnegative. ::: The sample solution is 8 lines. *Note*: This function will be useful to test streams you define below. *Note*: `stream_first_k_such_that` will run forever if `f` returns `false` for all elements of `s` except a finite number less than `k`. This is expected. ## **Problem 6** :::success Write a stream `funny_number_stream` that is like the stream of positive natural numbers (i.e., 1, 2, 3, 4, ...) except that numbers divisible by 6 are negated (i.e., 1, 2, 3, 4, 5, -6, 7, 8, 9, 10, 11, -12, 13, ...). ::: The sample solution is 4 lines. :::info Hint: Remember that the argument to the `Stream` constructor is a thunk that returns a pair. The first element of this pair will be a number and the second argument will be another stream. ::: ## **Problem 7** :::success Write a stream `foo_then_bar`, where the elements of the stream alternate between the strings `”foo”` and `”bar”`, starting with `”foo”`. ::: The sample solution is 4 lines. ## **Problem 8** :::success Write a function `cycle_lists` that takes two lists `xs` and `ys` and returns a stream. The lists may or may not be the same length, but assume they are both non-empty. The elements produced by the streams are pairs where the first component is from `xs` and the second component is from `ys`. The stream cycles forever through the lists. ::: For example, if `xs` is `[1;2;3]` and `ys` is `[“a”;”b”]`, then the stream would produce `[(1, "a"); (2, "b"); (3, "a"); (1, "b"); (2, "a"); (3, "b"); (1, "a"); (2, "b")]` The sample solution is 4 lines, but is more complicated than the previous stream problems. :::info *Hint*: Use one of the functions you wrote in Part 1. ::: :::info *Hint*: Use a recursive helper function that takes a number `n` and calls itself with `n + 1` inside a thunk. ::: --- # **Summary** Evaluating a correct assignment solution should generate these bindings *or more general types* in addition to the bindings from the provided code. ```ocaml val sequence : int -> int -> int -> int list val list_nth_mod : 'a list -> int -> 'a val array_assoc : 'a -> ('a * 'b) option array -> 'b option val caching_assoc : ('a * 'b) list -> int -> 'a -> 'b option val stream_first_k_such_that : ('a -> bool) -> int -> 'a stream -> 'a list val funny_number_stream : int stream val foo_then_bar : string stream val cycle_lists : 'a list -> 'b list -> ('a * 'b) stream ``` Note all functions use currying for multiple arguments. Generating these bindings does not guarantee that your solutions are correct. # Submission Submit the following **3 files** on **Gradescope**: :::success - `a6.ml` - `a6test.ml` - A `README.txt` or `README.md` file that answers the following: - Roughly how long did this assignment take you (in hours)? - Which was the most challenging problem? - Which your favorite problem? - Which resources did you find to be the most useful? :::