2

I'm working on this problem, where the propositional logic formula is represented by: 

datatype fmla =
     F_Var of string
   | F_Not of fmla
   | F_And of fmla * fmla
   | F_Or of fmla * fmla

Im trying to write a function that returns the size of a propositional-logic formula. A propositional variable has size 1; logical negation has size 1 plus the size of its sub-formula; logical conjunction and disjunction have size 1 plus the sizes of their sub-formulas.

How would I go about trying to solve this problem?

sshine
  • 15,635
  • 1
  • 41
  • 66
MasterYork42
  • 228
  • 2
  • 11

1 Answers1

5

In general, when you have a sum type like this, it can be a good idea to start with a function definition that just lists each case but leaves out the implementation:

fun size (F_Var v) =
  | size (F_Not f) =        
  | size (F_And (f1, f2)) =
  | size (F_Or (f1, f2)) =

and then you fill in the definitions of the cases one at a time as you figure them out.

Since you already have a list of what the size is in each case;

  • A propositional variable has size 1.
  • A negation has size 1 plus the size of its sub-formula.
  • A conjunction has size 1 plus the sum of the sizes of its sub-formulas.
  • A disjunction has size 1 plus the sum of the sizes of its sub-formulas.

you can pretty much translate it directly into ML:

fun size (F_Var _) = 1
  | size (F_Not f) = 1 + size f
  | size (F_And (f1, f2)) = ...
  | size (F_Or (f1, f2)) = ...

where I have left two cases for you to fill in.
Note that there is a very close correspondence between the definition in English and the definition in ML of each case.

molbdnilo
  • 64,751
  • 3
  • 43
  • 82
  • Thank You I was able to get size from this! Im running into an issue on a follow up question to this one. Its a function that returns a list of all the variables in the function. Ex: [a,b,c,e]. Im confused on how to create a list for the function since one is not given, and how to prevent duplicated from coming in. – MasterYork42 Mar 08 '18 at 21:27
  • @MasterYork42 Follow the same method: start with writing down the list of variables in `F_Var v`, then `F_Not f`, and so on Then you need a function that merges two lists so that the result doesn't have duplicates that you can use instead of appending. (You've probably seen something similar in an earlier exercise.) – molbdnilo Mar 09 '18 at 04:49