Exercises

Mandatory exercises

None.

Recommended exercises

• Exercise 2: multiplying all the payloads in a binary tree of integers using an accumulator
• Exercise 3: testing whether a given binary tree of integers represents a well-balanced mobile, using an exception instead of an option type
• Exercise 6: making an imperative list stutter
• Exercise 7: prepending the reverse of a list to another list
• Exercise 8: postpending a list to the reverse of another list

More exercises

The following exercises aim at solidifying one’s understanding and appreciation of exceptions.

Exercise 9

In the accompanying resource file, the function denoted by list_tail is purported to compute the suffix of a given list. Crystallize this computation by implementing an asorted unit-test function.

Harald: Now what.

Alfrothul: You mean asorted?

Harald: Is that a technical term?

Brynja: Not.

Halcyon: Derek and the Dominos, anyone?

Exercise 10

Let us revisit the insertion of an integer in a strictly sorted list of integers, i.e., a list of integers without repetition (see Exercise 16 and the subsequent bit After hours in Week 08). The twist here is that if the given integer to be inserted already occurs in the given list, we would like the result to be identical (not just structurally equal) to the given list.

1. Explain, in your own words, the design of the unit-test function denoted by test_insert_int_in_sorted_int_list in the accompanying resource file.

2. Explain why the function denoted by insert_int_in_sorted_int_list_v0 in the accompanying resource file does not pass the unit tests.

3. The accompanying resource file also contains the following definition:

   let insert_int_in_sorted_int_list_v1 n_given ns_given =
     if list_ormap (fun n -> n = n_given) ns_given
     then ns_given
     else insert_int_in_sorted_int_list_v0 n_given ns_given;;
   

   This function passes the unit tests. Why is that?

4. The function denoted by insert_int_in_sorted_int_list_v1 traverses the given list twice. Implement an OCaml function that inserts a given integer into a strictly sorted list of integers and that traverses the given list only once:

   let insert_int_in_sorted_int_list_v2 n_given ns_given =
     ...
   

5. To ensure that your implementation is structurally recursive, express it using a fold function:

   let insert_int_in_sorted_int_list_v2_alt n_given ns_given =
     ...
   

   (Hint: use parafold_right_list.)

   Your implementation may or may not pass the unit tests. If it does, yay. If it does not, why is that?

Version

Added Exercises 9 and 10 [17 Apr 2020]

Reorganized [24 Mar 2020]

Completed [30 Mar 2019]

Created [28 Mar 2019]