Минимизируйте скобки при печати выражения - PullRequest
Новая
       23

Минимизируйте скобки при печати выражения

6 голосов
/ 11 апреля 2020

У меня есть простая арифметическая c структура данных выражений, которую я хочу иметь возможность печатать. Для простоты здесь я сделал пример с 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)

Есть ли "легкий" принять это во внимание в экземпляре show? Я думаю, что мог бы сделать это, принимая во внимание все случаи, но это было бы взрывом функций. Есть какой-нибудь алгоритм или известный способ справиться с этим?

Надеюсь, у кого-нибудь есть указатели!

Спасибо.

1 Ответ

4 голосов
/ 11 апреля 2020

Экземпляр в терминах 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, но я не думаю, что есть какой-либо возможный способ исправить это, так как деление не разделяет это свойство, но поскольку оно имеет тот же приоритет, что и умножение, вы не можете различить guish их в 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

Я думаю, что это идеально. Все ваши тесты пройдены сейчас.

...