Exercises for Week 10

Exercise 00

1. The index of concepts for this week is in a separate chapter. Peruse it and make sure that its entries make sense to you (otherwise, click on them to check them out).
2. The lecture notes start with updates (Chapter Lecture Notes, updates). Make sure to check them out regularly, as they reflect the development of the lecture.
3. Time permitting, do peruse the lecture notes of this week, reproducing their OCaml content.

Mandatory exercises

The fourth wall: Friendly reminder – parentheses are for tuples, and square brackets are for lists.

• Exercise 00: perusing the index and checking the updates
• Exercise 01: about compare and make_comparison
• Exercise 02: computing the least integer contained in a given binary tree of integers
• Exercise 04: computing the weight a given binary tree of integers if these integers are positive
• Exercise 07: inverting the payloads in a binary tree of binary tree of integers
• Exercise 12: computing the least integer contained in a given binary tree of integers, generically
• Exercise 14: computing the weight a given binary tree of integers if these integers are positive, generically

Optional exercises

None.

Alfrothul: Figures.

Anton: Figures what?

Alfrothul (with a straight face): None is an option.

Practical exercise in preparation for Introduction to Data Structures and Algorithms

By design, OCaml programs need no type annotations: their syntax is enough to infer their type. In practice, though, facing a complicated type-error message, a judicious type annotation can go a long way towards understanding this error message. Also, other programming languages such as Haskell and Gallina require type annotations. And in the module that follows the present one (namely Introduction to Data Structures and Algorithms), all OCaml programs are written with type annotations, so that instead of writing:

let list_append xs_given ys_given =
  let rec visit xs =
    match xs with
    | [] ->
       ys_given
    | x :: xs' ->
       x :: visit xs'
  in visit xs_given;;

one writes:

let list_append (xs_given : 'a list) (ys_given : 'a list) : 'a list =
  let rec visit (xs : 'a list) : 'a list =
    match xs with
    | [] ->
       ys_given
    | x :: xs' ->
       x :: visit xs'
  in visit xs_given;;

In other words, all the formal parameters and all the results of each named function are annotated with their expected type, as foreshadowed in the practical note about let-declarations in Week 03 and as mentioned in the section about the power and limitations of aliasing types in Week 10.

In this light, you are asked to annotate all the formal parameters and all the results of all the functions in the accompanying file.

Pablito: There is nothing challenging in this exercise, right?

Mimer: Right, it is a preparatory one for a subsequent module.

Loki: You mean there is a life after Intro to CS?

Dana: There is, Loki, there is. It’s called “Life after Birth”.

Halcyon: The birth of computer scientists, that’s us!

Anton and Alfrothul: Aww...

Version

Renamed the accompanying file for the practical exercise, thanks to Edward Liau’s eagle eye [03 Apr 2023]

Moved the practical exercise from Week 12 to Week 10 [24 Mar 2023]

Created [15 Oct 2022]