Mini-project about indexing data structures

The goal of this mini-project is to index strings, arrays, lists, lazy lists, streams, imperative lists, and binary trees.

The solutions for each question may vary from very short to semi-long. The questions about strings, arrays, lists, and streams are mandatory. The questions about lazy lists, imperative lists, and binary trees are marked as optional, but you need to solve one of them, and that is not optional.

Warning

Exceptions are a topic of study in Week 12 (Chapters Exceptions in OCaml and Programming using exceptions).

Indexing strings

The goal of this section is to index a string with a function of type string -> int -> char option:

1. from left to right

   Your implementation should satisfy the following unit tests:

   let test_string_index_left_to_right candidate =
     let b0 = (candidate "0123" 0 = Some '0')
     and b1 = (candidate "0123" 1 = Some '1')
     and b2 = (candidate "0123" 2 = Some '2')
     and b3 = (candidate "0123" 3 = Some '3')
     and b4 = (candidate "0123" 4 = None)
     and b5 = (candidate "0123" ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   

   So:

   1. implement a solution that uses String.get (which indexes a string) and String.length (which computes the length of a string)
   2. implement a solution that uses String.get and the exception Invalid_argument
   3. implement a solution that uses String.mapi and an exception

2. from right to left

   Your implementation should satisfy the following unit tests:

   let test_string_index_right_to_left candidate =
     let b0 = (candidate "3210" 0 = Some '0')
     and b1 = (candidate "3210" 1 = Some '1')
     and b2 = (candidate "3210" 2 = Some '2')
     and b3 = (candidate "3210" 3 = Some '3')
     and b4 = (candidate "3210" 4 = None)
     and b5 = (candidate "3210" ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   

   So:

   1. implement a solution that uses String.get and String.length
   2. implement a solution that uses String.get, String.length, and the exception Invalid_argument
   3. implement a solution that uses String.mapi, String.length, and an exception.

Indexing arrays

• Whereas a string hosts characters and provides an index function (String.get) that works in constant time, an array hosts arbitrary OCaml values (of the same type) and provides an index function (Array.get) that works in constant time. Strings and arrays have a fixed size.
• Whereas a list hosts arbitrarily many OCaml values (of the same type), an array hosts a fixed number of OCaml values (of the same type). Indexing a list is carried out in linear time, whereas indexing an array is carried out in constant time.

The goal of this section is to index an array with a function of type 'a array -> int -> 'a option:

1. from left to right

   Your implementation should satisfy the following unit tests:

   let test_array_index_left_to_right_int candidate =
     let b0 = (candidate [|0; 1; 2; 3|] 0 = Some 0)
     and b1 = (candidate [|0; 1; 2; 3|] 1 = Some 1)
     and b2 = (candidate [|0; 1; 2; 3|] 2 = Some 2)
     and b3 = (candidate [|0; 1; 2; 3|] 3 = Some 3)
     and b4 = (candidate [|0; 1; 2; 3|] 4 = None)
     and b5 = (candidate [|0; 1; 2; 3|] ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   
   let test_array_index_left_to_right_char candidate =
     let b0 = (candidate [|'a'; 'b'; 'c'; 'd'|] 0 = Some 'a')
     and b1 = (candidate [|'a'; 'b'; 'c'; 'd'|] 1 = Some 'b')
     and b2 = (candidate [|'a'; 'b'; 'c'; 'd'|] 2 = Some 'c')
     and b3 = (candidate [|'a'; 'b'; 'c'; 'd'|] 3 = Some 'd')
     and b4 = (candidate [|'a'; 'b'; 'c'; 'd'|] 4 = None)
     and b5 = (candidate [|'a'; 'b'; 'c'; 'd'|] ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   

   So:

   1. implement a solution that uses Array.get (which indexes an array) and Array.length (which computes the length of an array)
   2. implement a solution that uses Array.get and the exception Invalid_argument

2. from right to left

   Your implementation should satisfy the following unit tests:

   let test_array_index_right_to_left_int candidate =
     let b0 = (candidate [|3; 2; 1; 0|] 0 = Some 0)
     and b1 = (candidate [|3; 2; 1; 0|] 1 = Some 1)
     and b2 = (candidate [|3; 2; 1; 0|] 2 = Some 2)
     and b3 = (candidate [|3; 2; 1; 0|] 3 = Some 3)
     and b4 = (candidate [|3; 2; 1; 0|] 4 = None)
     and b5 = (candidate [|3; 2; 1; 0|] ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   
   let test_array_index_right_to_left_char candidate =
     let b0 = (candidate [|'d'; 'c'; 'b'; 'a'|] 0 = Some 'a')
     and b1 = (candidate [|'d'; 'c'; 'b'; 'a'|] 1 = Some 'b')
     and b2 = (candidate [|'d'; 'c'; 'b'; 'a'|] 2 = Some 'c')
     and b3 = (candidate [|'d'; 'c'; 'b'; 'a'|] 3 = Some 'd')
     and b4 = (candidate [|'d'; 'c'; 'b'; 'a'|] 4 = None)
     and b5 = (candidate [|'d'; 'c'; 'b'; 'a'|] ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   

   So:

   1. implement a solution that uses Array.get and Array.length
   2. implement a solution that uses Array.get, Array.length, and the exception Invalid_argument

Indexing lists

The goal of this section is to index a list with a function of type 'a list -> int -> 'a option.

1. from left to right

   Your implementation should satisfy the following unit tests:

   let test_list_index_left_to_right_int candidate =
     let b0 = (candidate [0; 1; 2; 3] 0 = Some 0)
     and b1 = (candidate [0; 1; 2; 3] 1 = Some 1)
     and b2 = (candidate [0; 1; 2; 3] 2 = Some 2)
     and b3 = (candidate [0; 1; 2; 3] 3 = Some 3)
     and b4 = (candidate [0; 1; 2; 3] 4 = None)
     and b5 = (candidate [0; 1; 2; 3] ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   
   let test_list_index_left_to_right_char candidate =
     let b0 = (candidate ['a'; 'b'; 'c'; 'd'] 0 = Some 'a')
     and b1 = (candidate ['a'; 'b'; 'c'; 'd'] 1 = Some 'b')
     and b2 = (candidate ['a'; 'b'; 'c'; 'd'] 2 = Some 'c')
     and b3 = (candidate ['a'; 'b'; 'c'; 'd'] 3 = Some 'd')
     and b4 = (candidate ['a'; 'b'; 'c'; 'd'] 4 = None)
     and b5 = (candidate ['a'; 'b'; 'c'; 'd'] ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   

   So:

   1. implement a solution that uses List.nth and List.length
   2. implement a solution that uses List.nth and an exception
   3. implement a solution that is structurally recursive on the list,
   4. express your solution (for c.) with list_fold_right
   5. implement a solution that is structurally recursive on the index,
   6. express your solution (for e.) with nat_fold_right

2. from right to left

   Your implementation should satisfy the following unit tests:

   let test_list_index_right_to_left_int candidate =
     let b0 = (candidate [3; 2; 1; 0] 0 = Some 0)
     and b1 = (candidate [3; 2; 1; 0] 1 = Some 1)
     and b2 = (candidate [3; 2; 1; 0] 2 = Some 2)
     and b3 = (candidate [3; 2; 1; 0] 3 = Some 3)
     and b4 = (candidate [3; 2; 1; 0] 4 = None)
     and b5 = (candidate [3; 2; 1; 0] ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   
   let test_list_index_right_to_left_char candidate =
     let b0 = (candidate ['d'; 'c'; 'b'; 'a'] 0 = Some 'a')
     and b1 = (candidate ['d'; 'c'; 'b'; 'a'] 1 = Some 'b')
     and b2 = (candidate ['d'; 'c'; 'b'; 'a'] 2 = Some 'c')
     and b3 = (candidate ['d'; 'c'; 'b'; 'a'] 3 = Some 'd')
     and b4 = (candidate ['d'; 'c'; 'b'; 'a'] 4 = None)
     and b5 = (candidate ['d'; 'c'; 'b'; 'a'] ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   

   So:

   1. implement a solution that uses List.nth and List.length
   2. implement a solution that uses List.rev
   3. implement a solution that is structurally recursive on the list (if you think of several solutions, by all means document them)
   4. express your solution(s) (for c.) with list_fold_right

Subsidiary questions:

1. assuming you have [a solution for indexing a list from left to right] that uses list_fold_right, what do you obtain if you replace list_fold_right by list_fold_left?
2. assuming you have [a solution for indexing a list from right to left] that uses list_fold_right, what do you obtain if you replace list_fold_right by list_fold_left?

Indexing lazy lists (optional)

The goal of this section is to index a lazy list with a function of type 'a llist -> int -> 'a option, where the polymorphic type llist is defined as follows:

type 'a llist =
  | Lnil
  | Lcons of 'a * 'a llist Lazy.t;;

1. from left to right

   Your implementation should satisfy the following unit tests:

   let test_llist_index_left_to_right_int candidate =
     let b0 = (candidate (Lcons (0, lazy (Lcons (1, lazy (Lcons (2, lazy (Lcons (3, lazy Lnil)))))))) 0 = Some 0)
     and b1 = (candidate (Lcons (0, lazy (Lcons (1, lazy (Lcons (2, lazy (Lcons (3, lazy Lnil)))))))) 1 = Some 1)
     and b2 = (candidate (Lcons (0, lazy (Lcons (1, lazy (Lcons (2, lazy (Lcons (3, lazy Lnil)))))))) 2 = Some 2)
     and b3 = (candidate (Lcons (0, lazy (Lcons (1, lazy (Lcons (2, lazy (Lcons (3, lazy Lnil)))))))) 3 = Some 3)
     and b4 = (candidate (Lcons (0, lazy (Lcons (1, lazy (Lcons (2, lazy (Lcons (3, lazy Lnil)))))))) 4 = None)
     and b5 = (candidate (Lcons (0, lazy (Lcons (1, lazy (Lcons (2, lazy (Lcons (3, lazy Lnil)))))))) ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   
   let test_llist_index_left_to_right_char candidate =
     let b0 = (candidate (Lcons ('a', lazy (Lcons ('b', lazy (Lcons ('c', lazy (Lcons ('d', lazy Lnil)))))))) 0 = Some 'a')
     and b1 = (candidate (Lcons ('a', lazy (Lcons ('b', lazy (Lcons ('c', lazy (Lcons ('d', lazy Lnil)))))))) 1 = Some 'b')
     and b2 = (candidate (Lcons ('a', lazy (Lcons ('b', lazy (Lcons ('c', lazy (Lcons ('d', lazy Lnil)))))))) 2 = Some 'c')
     and b3 = (candidate (Lcons ('a', lazy (Lcons ('b', lazy (Lcons ('c', lazy (Lcons ('d', lazy Lnil)))))))) 3 = Some 'd')
     and b4 = (candidate (Lcons ('a', lazy (Lcons ('b', lazy (Lcons ('c', lazy (Lcons ('d', lazy Lnil)))))))) 4 = None)
     and b5 = (candidate (Lcons ('a', lazy (Lcons ('b', lazy (Lcons ('c', lazy (Lcons ('d', lazy Lnil)))))))) ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   

   So:

   1. implement a solution that is structurally recursive on the lazy list
   2. optionally, express your solution (for a.) with llist_fold_right, the fold-right function associated to lazy lists
   3. implement a solution that is structurally recursive on the index
   4. express your solution (for c.) with nat_fold_right

2. from right to left

   Your implementation should satisfy the following unit tests:

   let test_llist_index_right_to_left_int candidate =
     let b0 = (candidate (Lcons (3, lazy (Lcons (2, lazy (Lcons (1, lazy (Lcons (0, lazy Lnil)))))))) 0 = Some 0)
     and b1 = (candidate (Lcons (3, lazy (Lcons (2, lazy (Lcons (1, lazy (Lcons (0, lazy Lnil)))))))) 1 = Some 1)
     and b2 = (candidate (Lcons (3, lazy (Lcons (2, lazy (Lcons (1, lazy (Lcons (0, lazy Lnil)))))))) 2 = Some 2)
     and b3 = (candidate (Lcons (3, lazy (Lcons (2, lazy (Lcons (1, lazy (Lcons (0, lazy Lnil)))))))) 3 = Some 3)
     and b4 = (candidate (Lcons (3, lazy (Lcons (2, lazy (Lcons (1, lazy (Lcons (0, lazy Lnil)))))))) 4 = None)
     and b5 = (candidate (Lcons (3, lazy (Lcons (2, lazy (Lcons (1, lazy (Lcons (0, lazy Lnil)))))))) ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   
   let test_llist_index_right_to_left_char candidate =
     let b0 = (candidate (Lcons ('d', lazy (Lcons ('c', lazy (Lcons ('b', lazy (Lcons ('a', lazy Lnil)))))))) 0 = Some 'a')
     and b1 = (candidate (Lcons ('d', lazy (Lcons ('c', lazy (Lcons ('b', lazy (Lcons ('a', lazy Lnil)))))))) 1 = Some 'b')
     and b2 = (candidate (Lcons ('d', lazy (Lcons ('c', lazy (Lcons ('b', lazy (Lcons ('a', lazy Lnil)))))))) 2 = Some 'c')
     and b3 = (candidate (Lcons ('d', lazy (Lcons ('c', lazy (Lcons ('b', lazy (Lcons ('a', lazy Lnil)))))))) 3 = Some 'd')
     and b4 = (candidate (Lcons ('d', lazy (Lcons ('c', lazy (Lcons ('b', lazy (Lcons ('a', lazy Lnil)))))))) 4 = None)
     and b5 = (candidate (Lcons ('d', lazy (Lcons ('c', lazy (Lcons ('b', lazy (Lcons ('a', lazy Lnil)))))))) ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   

   So:

   1. implement a solution that is structurally recursive on the lazy list (if you think of several solutions, by all means document them)
   2. express your solution(s) (for a.) with llist_fold_right

Indexing streams

The goal of this section is to index a stream with a function of type 'a stream -> int -> 'a option, where the polymorphic type stream is defined as follows:

type 'a stream =
  | Scons of 'a * 'a stream Lazy.t;;

1. from left to right
2. from right to left

Subsidiary question: Is the option type needed here? Why?

Indexing imperative lists (optional)

The goal of this section is to index a list with a function of type 'a ilist -> int -> 'a option.

1. from left to right

   Your implementation should satisfy the following unit tests:

   let test_ilist_index_left_to_right_int candidate =
     let b0 = (candidate (Icons (0, ref (Icons (1, ref (Icons (2, ref (Icons (3, ref Inil)))))))) 0 = Some 0)
     and b1 = (candidate (Icons (0, ref (Icons (1, ref (Icons (2, ref (Icons (3, ref Inil)))))))) 1 = Some 1)
     and b2 = (candidate (Icons (0, ref (Icons (1, ref (Icons (2, ref (Icons (3, ref Inil)))))))) 2 = Some 2)
     and b3 = (candidate (Icons (0, ref (Icons (1, ref (Icons (2, ref (Icons (3, ref Inil)))))))) 3 = Some 3)
     and b4 = (candidate (Icons (0, ref (Icons (1, ref (Icons (2, ref (Icons (3, ref Inil)))))))) 4 = None)
     and b5 = (candidate (Icons (0, ref (Icons (1, ref (Icons (2, ref (Icons (3, ref Inil)))))))) ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   
   let test_ilist_index_left_to_right_char candidate =
     let b0 = (candidate (Icons ('a', ref (Icons ('b', ref (Icons ('c', ref (Icons ('d', ref Inil)))))))) 0 = Some 'a')
     and b1 = (candidate (Icons ('a', ref (Icons ('b', ref (Icons ('c', ref (Icons ('d', ref Inil)))))))) 1 = Some 'b')
     and b2 = (candidate (Icons ('a', ref (Icons ('b', ref (Icons ('c', ref (Icons ('d', ref Inil)))))))) 2 = Some 'c')
     and b3 = (candidate (Icons ('a', ref (Icons ('b', ref (Icons ('c', ref (Icons ('d', ref Inil)))))))) 3 = Some 'd')
     and b4 = (candidate (Icons ('a', ref (Icons ('b', ref (Icons ('c', ref (Icons ('d', ref Inil)))))))) 4 = None)
     and b5 = (candidate (Icons ('a', ref (Icons ('b', ref (Icons ('c', ref (Icons ('d', ref Inil)))))))) ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   

   So:

   1. implement a solution that uses ilist_fold_right in the manner of ilength_v2
   2. implement a solution that uses ilist_fold_right and an exception, in the manner of ilength_v3, iappend, ireverse, and imap

2. from right to left

   Your implementation should satisfy the following unit tests:

   let test_ilist_index_right_to_left_int candidate =
     let b0 = (candidate (Icons (3, ref (Icons (2, ref (Icons (1, ref (Icons (0, ref Inil)))))))) 0 = Some 0)
     and b1 = (candidate (Icons (3, ref (Icons (2, ref (Icons (1, ref (Icons (0, ref Inil)))))))) 1 = Some 1)
     and b2 = (candidate (Icons (3, ref (Icons (2, ref (Icons (1, ref (Icons (0, ref Inil)))))))) 2 = Some 2)
     and b3 = (candidate (Icons (3, ref (Icons (2, ref (Icons (1, ref (Icons (0, ref Inil)))))))) 3 = Some 3)
     and b4 = (candidate (Icons (3, ref (Icons (2, ref (Icons (1, ref (Icons (0, ref Inil)))))))) 4 = None)
     and b5 = (candidate (Icons (3, ref (Icons (2, ref (Icons (1, ref (Icons (0, ref Inil)))))))) ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   
   let test_ilist_index_right_to_left_char candidate =
     let b0 = (candidate (Icons ('d', ref (Icons ('c', ref (Icons ('b', ref (Icons ('a', ref Inil)))))))) 0 = Some 'a')
     and b1 = (candidate (Icons ('d', ref (Icons ('c', ref (Icons ('b', ref (Icons ('a', ref Inil)))))))) 1 = Some 'b')
     and b2 = (candidate (Icons ('d', ref (Icons ('c', ref (Icons ('b', ref (Icons ('a', ref Inil)))))))) 2 = Some 'c')
     and b3 = (candidate (Icons ('d', ref (Icons ('c', ref (Icons ('b', ref (Icons ('a', ref Inil)))))))) 3 = Some 'd')
     and b4 = (candidate (Icons ('d', ref (Icons ('c', ref (Icons ('b', ref (Icons ('a', ref Inil)))))))) 4 = None)
     and b5 = (candidate (Icons ('d', ref (Icons ('c', ref (Icons ('b', ref (Icons ('a', ref Inil)))))))) ~-1 = None)
     in b0 && b1 && b2 && b3 && b4 && b5;;
   

Subsidiary question:

1. assuming you have [a solution for indexing an imperative list from left to right] that uses ilist_fold_right, what do you obtain if you replace ilist_fold_right by ilist_fold_left?
2. assuming you have [a solution for indexing an imperative list from right to left] that uses ilist_fold_right, what do you obtain if you replace ilist_fold_right by ilist_fold_left?

Indexing binary trees (optional)

This section assumes that Exercise 7, in Week 13, was solved. Its goal is to index a binary tree with a function of type 'a binary_tree -> int -> 'a option, where the polymorphic type binary_tree is defined as follows:

type 'a binary_tree =
  | Leaf of 'a
  | Node of 'a binary_tree * 'a binary_tree;;

The tree traversals should be:

1. depth-first from left to right (provide two solutions: one which is structurally recursive, and one that isn’t)
2. depth-first from right to left (provide two solutions: one which is structurally recursive, and one that isn’t)
3. breadth-first from left to right
4. breadth-first from right to left

Resources

• The OCaml code for the present mini-project (latest version: 15 Apr 2021).

Version

Fixed the statement of Question 2.b in the section about indexing arrays, thanks to Marcellinus Jerricho’s keen eye [16 Apr 2021]

Fixed a typo in a test for lazy lists, thanks to Akanksha Chokshi and Le Nguyen Phong’s eagle eye [15 Apr 2021]

Added a collection of unit-test functions using the char type, not only the int type [14 Apr 2021]

Fixed the reference to Exercise 7, thanks to Aditya Singhania’s eagle eye [12 Apr 2021]

Adjusted the type of the indexing function in the question about Indexing streams as well as the optional questions [11 Apr 2021]

Created [03 Apr 2021]