CS 440 HW1

In this homework, you will be implementing a number of different OCaml functions that make use of recursion (tail and non-tail), manipulate lists, and perform pattern matching.

All the code you write for this homework will go into the "hw1.ml" file, found in the private source repository created when you accepted my GitHub invitation. In that file you will find stubs for each of the programming exercises described below. Each stub will have raise Unimplemented so that the file compiles. Remove that and add your code.

Collaboration

This assignment is to be completed individually, subject to the academic integrity policy on the course website. Make sure you read and understand these.

At the end of this assignment, we will ask you to list any students you discussed the homework with, as well as any websites or other resources (please list specific URLs when applicable) you referred to.

Important notes about grading

Your submissions will be graded automatically for correctness, as well as checked by hand. Please keep our autograder (and Xincheng, who has to run it) happy:

Do not change or remove any lines that start with (*>*.
Do not change the names or types of any functions defined in the starter code. (You can add helper functions if you want.)

Exercises

Each exercise below requires you to implement a single function. Unless explicitly mentioned, you should not use any built-in functions or special forms not covered in the first six lectures (through Thursday, Jan. 26). If you wish, however, you may implement additional helper functions on top of the required ones.

Note that some exercises specify whether your solution should be tail-recursive (or not). If unspecified, you may do either.

Each exercise is worth 5 points, for a total of 40 possible points.

iexpt: Performs integer exponentiation (assuming positive, integer arguments). Given arguments n and e, computes n^e. E.g.,
```
 # iexpt 2 10;;
 - : int = 1024

 # iexpt 5 3;;
 - : int = 125
```

poly_eval: Given coeffs and x, where coeffs is a list of integer coefficients (a, b, c, ...) and x is an integer, computes the value of the polynomial ax⁰ + bx¹ + cx² + ... E.g.,
```
 # poly_eval [2; 3; 4] 2;;
 - : int = 24

 # poly_eval [] 10;;
 - : int = 0

 # poly_eval [8; 4; 2; 1] 4;;
 - : int = 120
```
Your implementation should be tail-recursive. You may use iexpt from the previous exercise.
concatenate: Given a list of lists, concatenates all the elements of the argument lists into a single list. E.g.,
```
 # concatenate [[1; 2; 3]; [4]; [5; 6]];;
 - : int list = [1; 2; 3; 4; 5; 6]

 # concatenate [['h'; 'e']; ['l']; []; ['l'; 'o']];;
 - : char list = ['h'; 'e'; 'l'; 'l'; 'o']
```
Your implementation should be tail-recursive. Additionally, when building your result list, you should only use cons (::), and your implementation should have linear runtime w.r.t. the total number of elements. Hint: it might be helpful to use List.rev at some point in your implementation!
merge: Takes two argument lists, both of which contain only integers and are in ascending order. Returns a single list containing all the integers, sorted in ascending order. E.g.,
```
 # merge [1; 4; 8; 10] [2; 3; 7; 13];;
 - : int list = [1; 2; 3; 4; 7; 8; 10; 13]
```
Your implementation should not be tail-recursive (we'll do that next).
merge_tail: re-implement the previous function, but this time your implementation should be tail-recursive. As with your implementation of concatenate, you may only use the :: constructor to build your result list, and it should have linear runtime w.r.t. the total number of integers.
run_length_encode: returns a run-length encoding of the argument list. Run-length encoding stores each value together with the number of times it appears (contiguously) — in this way, a value that is repeated multiple times can be more efficiently represented. E.g.,
```
 # run_length_encode ['a'; 'a'; 'a'; 'a'; 'a'; 'b'; 'b'; 'b'];;
 - : (char * int) list = [('a', 5); ('b', 3)]

 # run_length_encode [1; 1; 6; 6; 6; 6; 2];;
 - : (int * int) list = [(1, 2); (6, 4); (2, 1)]

 # run_length_encode [];;
 - : ('a * int) list = []
```
Your implementation should be tail recursive. You may assume that adjacent elements can be compared for equality using =.

run_length_decode: given a run-length encoded list argument, returns the original list. E.g.,

 # run_length_decode [('a', 5); ('b', 3)];;
 - : char list = ['a'; 'a'; 'a'; 'a'; 'a'; 'b'; 'b'; 'b']

split: splits a list of pairs into a pair of lists; the first returned list contains the first components of all of the input pairs, and the second list contains all of the second components, e.g.
```
 # split [(1, 2); (3, 4); (5, 6)];;
 - : int list * int list = ([1; 3; 5], [2; 4; 6])
 # split [('a', 1); ('b', 2)];;
 - : char list * int list = (['a'; 'b'], [1; 2])
 # split [];;
 - : 'a list * 'b list = ([], [])
```
Your implementation does not need to be tail recursive.

Testing

We've provided you with tests for every exercise below the code stub. These tests use assert, like we saw in class. For example:

    let _ = assert (iexpt 1 15 = 1)
    let _ = assert (iexpt 5 0 = 1)
    let _ = assert (iexpt 2 10 = 1024)
    let _ = assert (iexpt 5 3 = 125)

You can run the test cases by compiling and running the file. In the hw1-<username> folder, run:

    make
    ./hw1

Recall that the first command compiles the program and reports any syntax or type errors. If there were none, the second command runs the program, including the assert tests. If an assert fails, you'll see an error like:

    Fatal error: exception Assert_failure("hw1.ml", 9, 8)

which means an assertion failed on line 9. Note that if you've left some functions unimplemented, you may instead see:

    Fatal error: exception Hw1.Unimplemented

This means an assertion tried to run a function you haven't implemented yet, tripping the raise Unimplemented. It also means that any assertions earlier in the file than the raise Unimplemented passed. (Note: if you do the exercises out of order and want to test assertions on later exercises without implementing earlier ones, comment out the code stub and assertion tests for the earlier exercise(s). Make sure to uncomment these before you submit.)

Note that while passing all the tests is a good indication that your solutions are on the right track, we don't guarantee exhaustive test coverage, nor that passing all tests will result in 100% on the assignment. You can (and probably should!) write your own additional tests to cover other cases. We may also run your code on tests we didn't provide, and will also be checking that, e.g., functions specified to be tail-recursive are implemented tail-recursively.

Extra questions

These questions are worth 0 points, but are nevertheless important (especially question 9).

Fill in students_collaborated_with with a list of strings giving the names of other students with whom you discussed this homework, and urls_consulted with a (string) list of web URLs or other resources you consulted while doing the homework. Be as specific and thorough as possible, within reason. Remember that this helps clear up confusion if we have any questions about your work. If either answer is "None", you should still fill in the empty list ([]).
Also fill in minutes_worked with the (approximate) number of minutes you spent working on this assignment. Your honest feedback will help us with future assignments.

Submission

When you are done with your work, make sure you have compiled your code using make (and ideally tested it using the instructions above). Submissions that do not compile will receive no credit. When finished, simply commit your changes and push them to our shared private GitHub repository. Please note that your submission date will be based on your most recent push (unless you let us know to grade an earlier version).

Make sure to git add hw1.ml before you commit so we see your changes, and make sure to git push. Double check Github and make sure you can see your latest code. There are no automatic tests this time.