haskell - 打印表达式时最小化括号

Question

我有一个简单的算术表达式数据结构，我希望能够打印它。为了简单起见，我在这里做了一个例子，其中包含 3 个二进制运算，加法、乘法和除法。定义如下所示:

module ExprPrint where

import Text.Printf

data Expr = Lit Int
          | Add Expr Expr
          | Mul Expr Expr
          | Div Expr Expr

instance Show Expr where
  show (Lit x) = show x
  show (Add e1 e2) = printf "(%s) + (%s)" (show e1) (show e2)
  show (Mul e1 e2) = printf "(%s) * (%s)" (show e1) (show e2)
  show (Div e1 e2) = printf "(%s) / (%s)" (show e1) (show e2)

我的目标是打印数据结构，同时删除所有多余的括号。当然，我上面实现的天真显示功能包括太多了。所以我想做的是制作 Show实例考虑操作的优先级(Div 和 Mul 超过 Add)和关联性(Add 和 Mul 是关联的，而 Div 是左关联的)。

这里有些例子:

one = Lit 1

-- Shows "((1) + (1)) + (1)" but should be 1 + 1 + 1
addAssoc = show $ Add (Add one one) one
-- Shows "((1) * (1)) * (1)" but should be 1 * 1 * 1
mulAssoc = show $ Mul (Mul one one) one
-- Shows "((1) / (1)) / (1)" but should be 1 / 1 / 1
divAssoc = show $ Div (Div one one) one
-- Shows "(1) / ((1) / (1)) but should be 1 / (1 / 1)
divAssoc2 = show $ Div one (Div one one)

-- Show "((1) * (1)) + (1)" but should 1 * 1 + 1
addPrec = show $ Add (Mul one one) one
-- Show "(1) + ((1) * (1))" but should show 1 + (1 * 1)
addPrec2 = show $ Add one (Mul one one)

在节目实例中是否有“容易”考虑到这一点？我认为我可以通过考虑所有情况来做到这一点，但这将是功能的爆炸式增长。有没有一些算法或已知的方法来处理这个？

希望有人指点一下!

谢谢。

Answer 1

show 中的一个实例不足以避免多余的括号，因为它没有任何关于可用优先级的信息。您需要根据 showsPrec 编写您的实例相反，它确实像这样:

module ExprPrint where

import Text.Show

data Expr = Lit Int
          | Add Expr Expr
          | Mul Expr Expr
          | Div Expr Expr

instance Show Expr where
  showsPrec prec (Lit x) = showsPrec prec x
  showsPrec prec (Add e1 e2) = showParen (prec >= 7) $ showsPrec 7 e1 . showString " + " . showsPrec 7 e2
  showsPrec prec (Mul e1 e2) = showParen (prec >= 8) $ showsPrec 8 e1 . showString " * " . showsPrec 8 e2
  showsPrec prec (Div e1 e2) = showParen (prec >= 8) $ showsPrec 8 e1 . showString " / " . showsPrec 8 e2

我为您的优先级选择了 6 和 7，因为这是 Haskell 自己使用的 + , * , 和 div运营商，但应该很明显您将如何选择不同的运营商。

至于关联性，通常没有完美的方法可以做到这一点，但是您可以在您的情况下通过一些优先级调整来伪造它，因为数学没有任何具有不同关联性的相同优先级的运算符。这是一个如何做到这一点的例子(我添加了 Exp ，优先级为 8，以给出一个右关联方式的例子):

module ExprPrint where

import Text.Show

data Expr = Lit Int
          | Add Expr Expr
          | Mul Expr Expr
          | Div Expr Expr
          | Exp Expr Expr

instance Show Expr where
  showsPrec prec (Lit x) = showsPrec prec x
  showsPrec prec (Add e1 e2) = showParen (prec >= 7) $ showsPrec 6 e1 . showString " + " . showsPrec 7 e2
  showsPrec prec (Mul e1 e2) = showParen (prec >= 8) $ showsPrec 7 e1 . showString " * " . showsPrec 8 e2
  showsPrec prec (Div e1 e2) = showParen (prec >= 8) $ showsPrec 7 e1 . showString " / " . showsPrec 8 e2
  showsPrec prec (Exp e1 e2) = showParen (prec >= 9) $ showsPrec 9 e1 . showString " ^ " . showsPrec 8 e2

这仍然不完美，因为它仍然不知道 Add 的关联属性。或 Mul , 所以 Mul one (Mul one one)将显示为 1 * (1 * 1)而不是 1 * 1 * 1 ，但我认为没有任何可能的方法来解决这个问题，因为除法不共享该属性，但由于它与乘法具有相同的优先级，因此您无法在 showsPrec 中区分它们.

实际上，您可以通过向下窥视并重新关联来欺骗更多:

module ExprPrint where

import Text.Show

data Expr = Lit Int
          | Add Expr Expr
          | Mul Expr Expr
          | Div Expr Expr
          | Exp Expr Expr

instance Show Expr where
  showsPrec prec (Lit x) = showsPrec prec x
  showsPrec prec (Add e1 (Add e2 e3)) = showsPrec prec (Add (Add e1 e2) e3)
  showsPrec prec (Add e1 e2) = showParen (prec >= 7) $ showsPrec 6 e1 . showString " + " . showsPrec 7 e2
  showsPrec prec (Mul e1 (Mul e2 e3)) = showsPrec prec (Mul (Mul e1 e2) e3)
  showsPrec prec (Mul e1 e2) = showParen (prec >= 8) $ showsPrec 7 e1 . showString " * " . showsPrec 8 e2
  showsPrec prec (Div e1 e2) = showParen (prec >= 8) $ showsPrec 7 e1 . showString " / " . showsPrec 8 e2
  showsPrec prec (Exp e1 e2) = showParen (prec >= 9) $ showsPrec 9 e1 . showString " ^ " . showsPrec 8 e2

我认为这是完美的。您的所有测试用例现在都通过了。