Exercise : Recursive structures

• Copy the type type ('a,'b) decision = | Result of 'b | Test of ('a -> bool) * ('a, 'b) decision * ('a, 'b) decision
  • It represents a decision diagram (or decision procedure).
  • It is a binary tree, where nodes are tests (like a IF), and leaves are results. In a node, Test (f, left, right) f is a predicate (a condition), the left subtree corresponds to the THEN branch, and the right subtree to the ELSE branch.
  • The type 'b is the type of results, whereas 'a is the type of the argument being tested.
  • Look at these examples to understand this type structure.
  let decision1 = Test ( (fun x -> x > 10), Result "Greater than 10", Result "Smaller or equal to 10" ) let decision2 = Test ( (fun x -> x < 100), decision1, Result "Big" ) (* decision1 is a subtree of decision2. *) let decision3 = Test ( (fun x -> x < 0), Result "Negative", decision2 ) (* decision2 is a subtree of decision3 *)
• Write a function apply_decision : α → (α, β) decision → β which takes a value and a decision tree and returns the result found by applying the tree to the value.

  apply_decision 0 decision3	"Smaller or equal to 10"
  apply_decision (-5) decision3	"Negative"
  apply_decision 99 decision3	"Greater than 10"
  apply_decision 100 decision3	"Big"

• Write a function map_decision : (α → β) → (γ, α) decision → (γ, β) decision such that map_decision f tree maps all results in the tree using the function f.

  map_decision String.length decision3	decision3, where results are ints instead of strings
  apply_decision 0 (map_decision String.length decision3)	22
  apply_decision 100 (map_decision String.length decision3)	3

• Write a function get_results : (α, β) decision → β list which returns a list of all results contained in the tree.

  get_results decision3

  [ "Big" ; "Smaller or equal to 10" ; "Greater than 10" ; "Negative" ]

  You may consider creating an auxiliary function with an accumulator.
• Write a function invert : (α, β) decision → (α, β) decision which inverts conditions and switches left and right subtrees (so that the decision procedure is equivalent). decision3 should become:
  

  let decision4 = invert decision3	Check that the tree is different from decision3.
  apply_decision 0 decision4	"Smaller or equal to 10"
  apply_decision (-5) decision4	"Negative"
  apply_decision 99 decision4	"Greater than 10"
  apply_decision 100 decision4	"Big"

Exercise : Exceptions

• We consider a type edecision which is an extension of the type decision used in the exercise above:
  type ('a,'b) edecision = | Result of 'b | Test of ('a -> bool) * ('a, 'b) edecision * ('a, 'b) edecision | Error of exn | Catch of ('a, 'b) edecision * (exn -> bool) * ('a, 'b) edecision
• The leaves Error e can now raise exceptions.
• A new node Catch (sub, epred, branch) acts like a try..with block: the subtree sub is computed. If it raises an exception ex, two cases are considered:
  • If the exception ex satisfies the predicate epred, then branch is computed.
  • Otherwise, the exception is propagated (raised again).
• Consider this example:
  let edecision1 = Test ( (fun x -> x > 10), Result "Greater than 10", Result "Smaller or equal to 10" ) let edecision2 = Test ( (fun x -> x < 100), edecision1, Error Not_found ) let edecision3 = Test ( (fun x -> x < 0), Error (Invalid_argument "Negative"), edecision2 ) let edecision4 = Catch ( edecision3, (function Not_found -> true | _ -> false), Result "Too big" )
• Write the function apply_edecision : α → (α, β) edecision → β which is similar to apply_decision, but handles also Error and Catch nodes.

  apply_edecision 0 edecision4	"Smaller or equal to 10"
  apply_edecision (-5) edecision4	Invalid_argument "Negative"
  apply_edecision 99 edecision4	"Greater than 10"
  apply_edecision 100 edecision4	"Too big"