haskell - 更好地显示 bool 公式

Question

我想实现一种在 SML 中显示命题公式的方法。到目前为止，我发现的解决方案是这种类型:

fun show (Atom a) = a
  | show (Neg p) = "(~ " ^ show p ^ ")"
  | show (Conj(p,q)) = "(" ^ show p ^ " & " ^ show q ^ ")"
  | show (Disj(p,q)) = "(" ^ show p ^ " | " ^ show q ^ ")";

这会产生不必要的大括号:

((~p) & (q | r))

什么时候，我想要的是:

~ p & (q | r)

我看到，Haskell 有一个函数(显示？)可以很好地做到这一点。有人可以帮我一下吗。我该怎么办？

Answer 1

如果要消除多余的括号，则需要传递一些优先级信息。例如，在 Haskell 中，showsPrec功能体现了这种模式；它有类型

showsPrec :: Show a => Int -> a -> String -> String

哪里第一 Int参数是当前打印上下文的优先级。额外的 String参数是获得有效列表附加的技巧。我将演示如何为您的类型编写一个类似的函数，尽管无可否认是在 Haskell 中(因为我最了解该语言)并且不使用额外的效率技巧。

这个想法是首先构建一个没有顶级括号的字符串——但确实有消除子项歧义所需的所有括号——然后仅在必要时添加括号。 unbracketed下面的计算是第一步。那么唯一的问题是:我们什么时候应该在我们的术语周围加上括号？好吧，答案是当低优先级术语是高优先级运算符的参数时，应该用括号括起来。所以我们需要比较我们的直接“父”的优先级——叫做 dCntxt在下面的代码中——按照我们当前呈现的术语的优先级——称为 dHere在下面的代码中。 bracket下面的函数根据比较的结果添加括号或单独保留字符串。

data Formula
    = Atom String
    | Neg  Formula
    | Conj Formula Formula
    | Disj Formula Formula

precedence :: Formula -> Int
precedence Atom{} = 4
precedence Neg {} = 3
precedence Conj{} = 2
precedence Disj{} = 1

displayPrec :: Int -> Formula -> String
displayPrec dCntxt f = bracket unbracketed where
    dHere       = precedence f
    recurse     = displayPrec dHere
    unbracketed = case f of
        Atom s   -> s
        Neg  p   -> "~ " ++ recurse p
        Conj p q -> recurse p ++ " & " ++ recurse q
        Disj p q -> recurse p ++ " | " ++ recurse q
    bracket
        | dCntxt > dHere = \s -> "(" ++ s ++ ")"
        | otherwise      = id

display :: Formula -> String
display = displayPrec 0

这是它的实际效果。

*Main> display (Neg (Conj (Disj (Conj (Atom "a") (Atom "b")) (Atom "c")) (Conj (Atom "d") (Atom "e"))))
"~ ((a & b | c) & d & e)"