Part 1: OCaml programming over trees
Create a file named quiz_2.ml to contain your solutions to the following problems. Note that the style of your functions will also be included in your assessment. These style issues to be assessed are the following:
• all top-level functions have complete type annontations
• all functions are properly indented
• all identifier names are appropriate and convey the intended meaning of their usage. For example, arguments to a function used in a fold or reduce function give some indication of their use.
Consider this tree type:
type ‘a tree = Leaf of ‘a
| Fork of ‘a tree * ‘a tree
Copy this type declaration into you quiz_2.ml file.
Make a tree, in any form you like, that has type int tree that contains the numbers 1, ,3, 4, 6, and 8. They can appear in any order in the tree.
Define it to have the name t as a let declaration in quiz_2.ml.
1. sum
Write a function called sum with type int tree -> int to add up all the numbers in the tree.
The following equalities should hold:
• sumt=22
• sum(Leaf4)=4
2. prod
Next write a function called prod with the same type as sum that multiples all the elements in an int tree tree together.
The following equalities should hold:
• prodt=576
• prod (Leaf 4) = 4
3. reduce
Write a reduce function, named reduce using the techniques described on Oct 21.
In your definition of reduce write a complete set of type annotations for the function so that the type of reduce is written out explicitly like we have done before.
4. sumr
Write a function named sumr that has the same type as sum and has the same behavior as sum but your sumr function must not be recursive and should consist of a call to your reduce function.
It should be that case that for any tree t, sum t = sumr t. 5. prodr
Write a function named prodr that has the same type as prod and has the same behavior as prod but your prodr function must not be recursive and should consist of a call to your reduce function.
It should be that case that for any tree t, prod t = prodr t.
6. string_of_int_tree
Write a non-recursive function named string_of_int_tree that converts all integer elements of a tree into strings and concatenates them together. This
function must consist of a call to your reduce function. You may also write helper functions if you wish to give nmes to the values passed into reduce if you find that
helpful.
The following equalities should hold:
• string_of_int_tree (Leaf 4) = “4”
• string_of_int_tree (Fork (Leaf 1, Leaf 23)) = “123”
• string_of_int_tree (Fork (Leaf 1, Fork (Leaf 2, Leaf 3))) = “123”
Recall the built-in function string_of_int with type int -> string and the operators ^ for string concatenation. Both might be helpful here.