Mini-project: 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.

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

   The 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

   The 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

   The 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

   The 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

   The 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 the solution for c. with list_fold_right
   5. implement a solution that is structurally recursive on the index,
   6. express the solution for e. with nat_fold_right

2. from right to left

   The 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, especially the ones that do not reverse the given list)
   4. express the solution(s) for c. with list_fold_right

Subsidiary questions:

1. assuming one of the solutions for indexing a list from left to right uses list_fold_right, what do we obtain if we replace list_fold_right by list_fold_left?
2. assuming one of solutions for indexing a list from right to left uses list_fold_right, what do we obtain if we replace list_fold_right by list_fold_left?

Indexing lazy lists

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

   The 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 the 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 the solution for c. with nat_fold_right

2. from right to left

   The 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 the 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

Indexing imperative lists

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

   The 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

   The 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 one of the solutions for indexing an imperative list from left to right uses ilist_fold_right, what do we obtain if we replace ilist_fold_right by ilist_fold_left?
2. assuming one of the solutions for indexing an imperative list from right to left uses ilist_fold_right, what do we obtain if we replace ilist_fold_right by ilist_fold_left?

Indexing binary trees

This mini-project builds on the mini-project about depth-first and breadth-first traversals. 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

Food for thought about indexing from left to right and from right to left

Since

• indexing a reversed string from left to right is equivalent to indexing this string from right to left,
• indexing a reversed array from left to right is equivalent to indexing this array from right to left,
• indexing a reversed list from left to right is equivalent to indexing this list from right to left,

is it possible to “reverse” a binary tree so that indexing this reversed tree from left to right is equivalent to indexing this tree from right to left? If so, what is this “reverse” transformation?

Resources

• The OCaml code for the present mini-project (latest version: 03 Nov 2022).

Version

Created [10 Jan 2023]