Mini-project about indexing data structures

The goal of this mini-project is to index strings, arrays, lists, lazy lists, streams, 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

   Your implementation should satisfy the following unit tests:

   let test_index_string_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

   Optionally, implement a solution that uses String.mapi (alias Stringy.mapi in the resource file) and an exception.

2. from right to left

   Your implementation should satisfy the following unit tests:

   let test_index_string_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

   Optionally, implement a solution that uses String.mapi (alias Stringy.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_index_array_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;;
   

   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_index_array_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;;
   

   So:

   1. implement a solution that uses Array.get and Array.length
   2. implement a solution that uses Array.get 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_index_list_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;;
   

   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 fold_right_list
   5. implement a solution that is structurally recursive on the index,
   6. express your solution (for e.) with fold_right_nat

2. from right to left

   Your implementation should satisfy the following unit tests:

   let test_index_list_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;;
   

   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 fold_right_list

Subsidiary questions:

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

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

   Your implementation should satisfy the following unit tests:

   let test_index_llist_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;;
   

   So:

   1. implement a solution that is structurally recursive on the lazy list
   2. optionally, express your solution (for a.) with fold_right_llist, 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 fold_right_nat

2. from right to left

   Your implementation should satisfy the following unit tests:

   let test_index_llist_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;;
   

   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 fold_right_llist

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 binary trees

This section assumes that Exercise 7, in Week 12, 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: 19 Apr 2020).

Version

Fixed the type of the stream-indexing functions so that its codomain has an option type, thanks to Chau Nguyen’s ever-vigilant eagle eye [06 May 2020]

Spelled out the questions some more and made the unit-test functions properly polymorphic, thanks to Koa Zhao Yuan’s eagle eye [19 Apr 2020]

Added error messages in the unit-test functions of the resource file [08 Apr 2020]

Created [04 Apr 2020]