标准 ML 中命题逻辑公式的大小

Question

我正在研究这个问题，其中命题逻辑公式表示为：

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

我正在尝试编写一个 returns 命题逻辑公式大小的函数。命题变量的大小为 1；逻辑否定的大小为 1 加上其子公式的大小；逻辑合取和析取的大小为 1 加上它们的子公式的大小。

我将如何尝试解决这个问题？

Answer 1

一般来说，当您有这样的求和类型时，最好从只列出每种情况但忽略实现的函数定义开始：

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

然后您在弄清楚案例时一次填写一个案例的定义。

因为您已经有了每种情况下尺寸的列表；

• 命题变量的大小为 1。
• 否定的大小为 1 加上它的大小 sub-formula。
• 合取的大小为 1 加上其 sub-formula 个大小的总和。
• 析取的大小为 1 加上其 sub-formula 的大小之和。

你几乎可以将它直接翻译成 ML:

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

我留下了两个案例让你填写。
请注意，每个案例的英文定义与 ML 中的定义之间存在非常密切的对应关系。