(* 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"
| ...