sml - 递归 pretty-print 表达式

Question

infix v;
infix &;
datatype s = P | Q | S
         | ~ of s
         | v of s * s
         | & of s * s;

我创建了一个函数 (s -> unit) 将类型 s 打印为字符串

fun printS(P) = print "P"
  | printS(Q) = print "Q"
  | printS(P & Q) = print "P & Q";

我的问题是，如果我有更复杂的 s，我该如何递归打印 s，例如 P v ~ Q & P.​​

Answer 1

您可以通过将子树作为变量进行模式匹配，然后引用这些子树，以递归方式漂亮地打印表达式。在您的示例中，您只匹配 P & Q 这恰好是一棵树。

fun printS P = print "P"
  | printS Q = print "Q"
  | printS S = print "S"
  | printS (p & q) = (print or printS ...; print or printS ...; ...)

通过不引用实际的 P 和 Q，而是引用变量 p 和 q，这些可以是任何子表达式。由于您的函数返回 unit，因此您需要打印多次。除非，您想要打印的某些内容是递归数据类型，因此您可以改用专门的 printS。

我可能会将其转换为字符串并打印一次:

fun toString P = "P"
  | toString Q = "Q"
  | toString S = "S"
  | toString (p & q) = "(" ^ toString p ^ " & " ^ toString q ^ ")"
  | toString ... = ...

然后打印出来:

fun printS s = print (toString s)

真正的挑战在于打印最少数量的括号:

printS ((P v Q) & (Q v P))

最好不要打印 P v Q & Q v P，因为它们不是相同的表达式。