(* defines natural numbers and formulas *) type nat = Z | S of nat type form = LEQF of nat * nat | TrueF | FalseF | AndF of form * form | OrF of form * form (* returns true if Leq n1 n2 *) let leq (n1:nat) (n2:nat) : bool = ... (* returns true if F Valid *) let isvalid (f:form) : bool = ... (* prints Z as "0", prints S Z as "1", prints S S S S S S Z as "6", etc. *) let printnat (n:nat) : unit = ... (* printform f should print f. nats should be printed using printnat as above /\ and \/ both associate to the left /\ has higher precendence than \/ so if you print false \/ 0 <= 1 /\ 1 <= 2 /\ 3 <= 4 then you meant: false \/ ((0 <= 1 /\ 1 <= 2) /\ 3 <=4) and not: (false \/ 0 <= 1) /\ (1 <= 2 /\ 3 <=4) The easy way to handle this is is to insert parentheses EVERYWHERE to disambiguate the structure of the formula. eg: (((1 <= 2) /\ (true)) \/ (false)) But it would be better if you are able to write the program so it outputs: 1 <= 2 /\ true \/ false Note: your first priority is to make sure your function is correct. Your second priority (and this part is OPTIONAL and worth BONUS POINTS) is to reduce the number of parentheses. Producing the optimal parenthesization is somewhat of a tricky problem. You'll have to spend time thinking about the algorithm before beginning to code (just tackling 1 or 2 special cases won't get you any points -- a good solution is one that handles the general case in an elegant way. If you've already spent a lot of time on this assignment, don't worry about this second priority. Please don't spend 10 hours just trying to solve this subpart of the problem unless you're having fun doing it. This part of the problem set is really for people who already have some experience programming in ML or Scheme and/or those who want a bit of a challenge. Suggestion for tackling optimal parenthesization: - Associate each formula type with an integer precedence (2 for /\ and 1 for \/) - Implement printform2 by introducing a helper function (printaux (preced, f)) to print formula f. When the top-most connective in f has lower precedence level than preced, print parentheses. *) let printform (f:form) : unit = match f with TrueF -> print_string "true" | FalseF -> print_string "false" | ...