Homework 1: Finger Exercises

This homework is designed to give you a basic feel for the OCaml language, including recursion and lists.

1. If you have not already done so in your recitation, follow the Codio OCaml Setup instructions

2. Visit the CIS 1200 course in codio and select the "HW01" project.

3. Open the file intro.ml and follow the directions there to complete the homework assignment.

   TIP: All of the homework is in intro.ml. You do not need to look at or edit any other file.

   The files for this homework are already available in the Codio project, but you can download a fresh copy if needed using this link: hw01.zip.

4. Once you are finished, be sure to Submit your homework submit.

FAQ

General Questions

1. What does FAQ stand for?

Frequently Asked Questions!

2. What should I read for help on this homework assignment?

Chapters 2, 3 and 4 of the lecture notes. Consider reviewing the lecture slides, too.

3. Help! I can’t compile! I can’t run tests! I get a strange error message!

See the project troubleshooting FAQ. This might help if you are using Codio.

4. For HW01, the grade we get online is our final grade, right? Points will not be deducted for style, commenting, etc on this homework?

You will meet with your TA to get feedback on your style, but style won’t count toward your grade for this homework. (It will for future homework assignments.)

5. Do we have to account for incorrect inputs by the user? For example, for problem #3, the direction will either be “forward” or “backward”. What if the user inputs “abcdeg” or 256? What if num_moves is negative?

Each problem will specify the range of inputs that your function should be able to handle, either in the type signature or comments in the file. If an input falls outside of this range (i.e. “abcdeg”) then your code may do anything it likes. Our test cases will not run your function with such inputs.

6. I’m trying to use print statements to debug my code, but am a little confused about how the ;; print_endline ... command works. Is there somewhere I can find more info on this?

The ;; print_endline ... command invokes print_endline, a function of type string -> unit (unit is a few sections ahead of where you’re expected to be right now, do you don’t need to understand what it means). The print_endline function takes a string and prints it to standard output. Since it expects a string as an argument, trying to print a string list with it won’t work. See here for more info on output functions.

Debugging with print statements is unwieldy in OCaml. Try writing specific test cases and tracing through your code by hand to help you debug :).

7. Can we use helper functions to separate out the problem into a few steps? For example, can I call another function inside problem 8 part 2 that iterates through the names?

You may certainly use helper functions. In fact, you may consider using functions you were asked to write earlier in the homework. In general, you are always allowed to write helper functions (unless we state otherwise). Whenever a complicated problem divides neatly into different parts, it’s a good idea to at least consider making use of a helper function.

8. Would an empty list, [ ] contain the empty string, "", technically speaking?

Nope, the empty list is totally empty—it doesn’t contain the empty string or anything else.

9. Is an empty list sorted? What about a list with only one element?

Yes, all the elements (i.e., all zero of them) are in order in both lists. Another way to think about this is to ask the reverse. Is an empty list unsorted – i.e., are there any elements that are out of order in an empty list?

10. I can’t test my code with a negative number! I get a strange error when I say coins -1

This is an OCaml quirk we’ll talk about more later in the semester. You need to put parentheses around negative numbers. i.e. coins (-1)

11. If the function header reads let rec ... does that mean that the function we write must be recursive? Do we need to remove the “rec” if it is not?

You do not need to use recursion if you think it is unnecessary. The rec keyword allows the function to be recursive but does not require to function to be recursive. We do not expect you to delete the rec keyword if your solution isn’t recursive.

11a. Can I add the “rec” keyword to a function that we’re provided?

No, but you can write helper functions that use the rec keyword.

12. Can I write a test case that checks that certain inputs should fail? For example, calling coins with a negative number?

Yes. If you say ;; run_failing_test "testname" test instead of run_test, then the test will pass only if a failwith occurs.

13. Do we have to comment our code?

The comments we’ve provided in this assignment should be sufficient to explain your code; you don’t need to add any more. However, as a general rule, comments should be included whenever your code is unclear or hard to follow without them.

14. Can we use the @ operator or List.append? Can we use any other functions from the OCaml List library?

No, not on this assignment.

The point of this homework is to practice writing functions on lists in OCaml. Finding a library function that solves the problem undermines that purpose. You can use functions from the List library on future homework assignments.

15. Can you give me tips on pattern matching?

A lot of people have questions about pattern matching and how to get the information you want out of a list. Pattern matching is a very useful feature of OCaml, and there are more possibilities than the simple [] and hd::tl patterns. For instance, say we wanted to return the last element of an integer list. We could do this:

let rec foo (l : int list) : int =
   begin match l with
   | [] -> failwith "empty list"
   | [x] -> x
   | hd::tl -> foo tl
   end

Or, say we wanted to return the the sum of the last two elements of an integer list. We could do this:

let rec foo (l : int list) : int =
   begin match l with
   | fst::snd::[] -> fst + snd
   | hd::tl -> foo tl
   | _ -> failwith "list has less than two elements"
   end

The underscore pattern here matches against any value. Therefore, it’s usually used as the last pattern to match against, working as a catch-all. However, it can also be nested inside of a more complex pattern. Consider a function that returns the length of a list:

let rec length (l : int list) : int =
   begin match l with
   | _::tl -> 1 + length tl
   | _ -> 0
   end

The head element of the list is irrelevant, as long as there is a head element. Hence the underscore in the first pattern. The second underscore catches all other cases that get past the first pattern. Which is only the empty list.

One common question is: Can I pattern-match two lists simultaneously? The answer is yes! In terms of syntax, you would just separate the two lists with a comma, including within the actual pattern match. Consider an example function (that doesn’t actually do anything of note) to see how the syntax looks:

let rec length (l1 : int list) (l2 : int list) : int =
   begin match l1, l2 with
   | hd1 :: tl1, hd2 :: tl2 -> 1
   ...
   end

Section 4.4 in the lecture notes goes more in depth with this, and also talks about tuples, which will give you even more ways to pattern match, and are useful in situations where you have two things you want to examine, like two lists.

16. Everything is highlighted in red and I am getting an error message “unbound module assert”. What does this mean?

This is usually due to a syntax error in your code, especially having an “if” and “then” with no “else”. If you don’t think you have any syntax errors, you should clean and build your project before running it again. If it runs with no errors, you can ignore the red lines. Codio is sometimes slow to update them.

17. What’s the difference between a failure and an error?

A failure means that your code produce and answer but the answer was incorrect. An error means that your code failed to produce an answer (perhaps by using failwith or by not having a complete pattern match, etc.)

Problem 6

18. On problem 6, I keep getting an error that states: This expression has type 'a list but is here used with type string. What does this mean?

You usually get an error message like that when you put a list where there was supposed to be a string. In particular, make sure you’re not using the :: operator where you should be using the ^ operator.

19. For problem 6, for a list containing one string, do we return the string itself or string plus separator?

You should not include the separator for a list of length 1.

Problem 8

20. For contains_str, do we need to account for capitalization?

Yes: “bear” is different from “Bear.”

21. For problem 8, if list 1 has two of the same values and that value also appears in list 2, should I output that value twice or only the first time it appears in list 1?

If the value appears twice in the first list then it will appear twice in the output list.

22. For in_both, does the returned list have to contain the names in the same order as they appeared in the first list? What if there are multiple occurrences of the same name?

Yes. And all occurrences should be in your output.

23. Should we assume that the first list will always have at least one name from the second in it?

No, your code needs to be able to handle the empty case.

24. How do we compare strings in OCaml? Is there something like .equals in Java?

The = operator in OCaml will perform a “structural equality check” between two strings (i.e., it will tell you whether they consist of the same sequence of characters). This is morally equivalent to the use of the .equals()method for the String class in Java.

25. Can we use List.hd if we are 100% sure that it will not throw an error?

No: don’t use anything from the List library. (Also, even if you were using it correctly here, pattern matching is better style. In future assignments, you will lose style points if you use List.hd.)

Problem 11

26. For problem 11, do we need to check that the given lists are sorted?

Nope! As stated in the problem description, your function assumes that it takes in 2 sorted lists as inputs.

Problem 12

27. For problem 12, OCaml is giving me an unbound value error when I call my helper function. What does this mean?

Is your helper function before or after the function you are trying to use your helper function in? Your helper function should be before the function you are trying to use your helper function in.

Grading

• There are 100 points possible on this assignment.
• You may submit without penalty up to 5 times.
• Each extra submission costs you 5 points.
• Please see our course syllabus for information about the late submission policy.
• Submissions will not be accepted more than 48 hours past the due date.

Style feedback: After submitting your homework, you must make an appointment with one of your recitation TAs to get feedback about your coding style. This meeting counts towards your class participation grade. Future assignments will count style as part of the homework grade.