Подтвердить что ты не робот

ShowPrec и приоритеты операторов

Я спрашивал об этом раньше, но, похоже, я сформулировал этот вопрос слишком узко. Поэтому давайте посмотрим, смогу ли я объяснить, что я на самом деле после.

Предположим, что у меня есть некоторый тип, который поддерживает несколько двоичных операторов, каждый из которых имеет различный приоритет и ассоциативность. Как написать экземпляр Show, который правильно скопирует подвыражения?

Я знаю, что я здесь плотный, но я ошибаюсь каждый раз, когда я пытаюсь это сделать. Должна быть какая-то механическая процедура, за которой вы можете следовать, чтобы сделать это правильно, но я не могу ее найти. Может ли кто-нибудь пройти меня через пример?

Я знаю, что это, в конечном счете, сводится к завершению всего в showParen и показу суб-выражений с использованием showsPrec с правильным магическим числом, и я могу заставить его почти работать, но он никогда не работает правильно при любых обстоятельствах.

Изменить: Рассмотрим следующий код

data Expr =
  Const Int |
  Expr :+: Expr |
  Expr :-: Expr |
  Expr :*: Expr |
  Expr :/: Expr

infixl 6 :+:
infixl 6 :-:
infixl 7 :*:
infixl 7 :/:

instance Show Expr where
  showsPrec p e0 =
    case e0 of
     Const n -> shows n
     x :+: y -> showParen (p > 6) $ (showsPrec 6 x) . (" :+: " ++) . (showsPrec 6 y)
     x :-: y -> showParen (p > 6) $ (showsPrec 6 x) . (" :-: " ++) . (showsPrec 6 y)
     x :*: y -> showParen (p > 7) $ (showsPrec 7 x) . (" :*: " ++) . (showsPrec 7 y)
     x :/: y -> showParen (p > 7) $ (showsPrec 7 x) . (" :/: " ++) . (showsPrec 7 y)

Это работает почти правильно:

*Main> Const 1 :+: Const 2 :*: Const 3 :+: Const 4
1 :+: 2 :*: 3 :+: 4
*Main> (Const 1 :+: Const 2) :*: (Const 3 :+: Const 4)
(1 :+: 2) :*: (3 :+: 4)

Но не совсем:

*Main> Const 1 :+: Const 2 :-: Const 3 :-: Const 4
1 :+: 2 :-: 3 :-: 4
*Main> Const 1 :+: Const 2 :-: (Const 3 :-: Const 4)
1 :+: 2 :-: 3 :-: 4

Итак, похоже, что приоритет в порядке, но ассоциативность увязывается.

4b9b3361

ОТВЕТЫ

Ответ 1

Так как showsPrec не имеет никакого способа получить ассоциативность контекста, я не думаю, что это можно исправить, как в, вернемся к минимальным скобкам Haskell. Чтобы обеспечить правильность без добавления избыточных парен, чем необходимо, используйте >= в showParen:

  showsPrec p e0 =
    case e0 of
     Const n -> shows n
     x :+: y -> showParen (p >= 6) $ (showsPrec 6 x) . (" :+: " ++) . (showsPrec 6 y)
     x :-: y -> showParen (p >= 6) $ (showsPrec 6 x) . (" :-: " ++) . (showsPrec 6 y)
     x :*: y -> showParen (p >= 7) $ (showsPrec 7 x) . (" :*: " ++) . (showsPrec 7 y)
     x :/: y -> showParen (p >= 7) $ (showsPrec 7 x) . (" :/: " ++) . (showsPrec 7 y)

Это значит, что

* Main > Const 1: +: Const 2: *: Const 3: +: Const 4
(1: +: 2: *: 3): +: 4
* Main > (Const 1: +: Const 2): *: (Const 3: +: Const 4)
(1: +: 2): *: (3: +: 4)
* Главная > Const 1: +: Const 2: -: Const 3: -: Const 4
((1: +: 2): -: 3): -: 4
* Главная > Const 1: +: Const 2: -: (Const 3: -: Const 4)
(1: +: 2): -: (3: -: 4)

Это выглядит не так хорошо, как могло бы, но не так уж плохо и, конечно, не так, как версия showParen (p > n). В принципе, это дает минимальную скобку, если бы мы имели только infix, no infixl или infixr.

Если вы хотите, чтобы появлялись только те парсеры, которые действительно необходимы, вам нужно будет распространять больше информации, чем просто Int для определения контекста. Я реализовал такую ​​вещь в моей идее расширения символики-математики для HaTeX; по сути, он просто отражает Haskell infixl и т.д. аннотации во время выполнения. Например,

     exaDisp $ 5 - (4 - 3) + 2 + 1

затем отображается как

Minimal-parenthesization in HaTeXMath

Ответ 2

Следующий экземпляр Show напечатает тип Expr с минимальными скобками:

data Expr =
  Const Int |
  Expr :+: Expr |
  Expr :-: Expr |
  Expr :*: Expr |
  Expr :/: Expr

infixl 6 :+:
infixl 6 :-:
infixl 7 :*:
infixl 7 :/:

instance Show Expr where
  showsPrec p e0 =
    case e0 of
     Const n -> showParen (p > 10) $ showString "Const " . showsPrec 11 n
     x :+: y -> showParen (p > 6) $ showsPrec 6 x . showString " :+: " . showsPrec 7 y
     x :-: y -> showParen (p > 6) $ showsPrec 6 x . showString " :-: " . showsPrec 7 y
     x :*: y -> showParen (p > 7) $ showsPrec 7 x . showString " :*: " . showsPrec 8 y
     x :/: y -> showParen (p > 7) $ showsPrec 7 x . showString " :/: " . showsPrec 8 y

Это приводит к:

*Main> Const 1 :+: Const 2 :*: Const 3 :+: Const 4
Const 1 :+: Const 2 :*: Const 3 :+: Const 4
*Main> (Const 1 :+: Const 2) :*: (Const 3 :+: Const 4)
(Const 1 :+: Const 2) :*: (Const 3 :+: Const 4)
*Main> Const 1 :+: Const 2 :-: Const 3 :-: Const 4
Const 1 :+: Const 2 :-: Const 3 :-: Const 4
*Main> Const 1 :+: Const 2 :-: (Const 3 :-: Const 4)
Const 1 :+: Const 2 :-: (Const 3 :-: Const 4)

Общее правило

  • infix n: используйте showParen (p > n), showsPrec (n+1) слева и showsPrec (n+1) справа
  • infixl n: используйте showParen (p > n), showsPrec n слева и showsPrec (n+1) справа
  • infixr n: используйте showParen (p > n), showsPrec (n+1) слева и showsPrec n справа
  • non-infix: используйте showParen (p > 10) и showsPrec 11 для аргументов

Следующее это правило всегда дает правильный синтаксис с минимальными скобками, за исключением одного угла: он может вызывать неоднозначный вывод, если у вас есть конструкторы infixl и infixr с одинаковым уровнем приоритета. Пока вы этого не делаете, вы должны быть в порядке.

Как я узнал, какие аргументы использовать с showParen? Он соответствует тому, что Haskell делает для производных экземпляров Show. Мы можем протестировать таких:

data T = P :# P | T P
  deriving Show

infix 6 :#

data P = P

instance Show P where
  showsPrec p P = shows p

Мы видим, что с infix 6 :# экземпляр Show T вызывает showsPrec 7 для аргументов :#, а также показывает круглые скобки только в приоритетах > 6:

*Main> showsPrec 6 (P :# P) ""
"7 :# 7"
*Main> showsPrec 7 (P :# P) ""
"(7 :# 7)"

И для обычного конструктора T сгенерированный экземпляр вызывает showsPrec 11 в аргументе и показывает parens в приоритетах > 10:

*Main> showsPrec 10 (T P) ""
"T 11"
*Main> showsPrec 11 (T P) ""
"(T 11)"

Ответ 3

Как насчет этого:

prec :: Expr -> Int
prec (Const _) = 10
prec (_ :*: _) = 7
prec (_ :/: _) = 7
prec (_ :+: _) = 6
prec (_ :-: _) = 6

instance Show Expr where
  showsPrec p e0 =
    case e0 of
     Const n -> shows n
     x :+: y -> showbin 6 " + " x y
     x :-: y -> showbin 6 " - " x y
     x :*: y -> showbin 7 " * " x y
     x :/: y -> showbin 7 " / " x y
    where showbin pr s x y =
            showParen (p > pr) $
             showsPrec pr x . (s ++) .
             showParen (prec y == pr) (showsPrec pr y)

в результате чего

*Main> (Const 1 :+: Const 2) :*: (Const 3 :+: Const 4)
(1 + 2) * (3 + 4)
*Main> Const 1 :+: Const 2 :-: Const 3 :-: Const 4
1 + 2 - 3 - 4
*Main> Const 1 :+: Const 2 :-: (Const 3 :-: Const 4)
1 + 2 - (3 - 4)
*Main> Const 1 :+: Const 2 :-: (Const 3 :-: Const 4 :-: Const 5)
1 + 2 - (3 - 4 - 5)
*Main> Const 1 :+: Const 2 :-: (Const 3 :-: (Const 4 :-: Const 5))
1 + 2 - (3 - (4 - 5))
*Main> Const 1 :+: Const 2 :-: (Const 3 :*: (Const 4 :/: Const 5))
1 + 2 - 3 * (4 / 5)
*Main> (Const 1 :*: (Const 2 :-: (Const 3 :*: (Const 4 :/: Const 5))))
1 * (2 - 3 * (4 / 5))