Красивое приложение для печати (лямбда-исчисление)

показывает Prec и приоритеты операторов имеет хорошее резюме:

• 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 справа.
• неинфиксный: используйте showParen (p > 10) и showsPrec 11 в аргументах

Причина в том, что параметр приоритета showsPrec представляет приоритет окружающего выражения, поэтому вам нужно включать круглые скобки, когда это выражение является оператором, который связывается более тесно, чем выражение, которое вы показываете. + 1 предназначен для того, чтобы рассматривать приоритет так, как если бы он был немного выше, чтобы выражения с одинаковым приоритетом получали круглые скобки при переопределении ассоциативности оператора.

По соглашению, реализации showsPrec обычно используют те же номера приоритета, что и обычный код Haskell, где 0 — самый низкий (как в f $ x), а 10 — самый высокий (как в f x). Вы можете проверить приоритет оператора с помощью :info в GHCi.

λ :info +
type Num :: * -> Constraint
class Num a where
  (+) :: a -> a -> a
  ...
        -- Defined in ‘GHC.Num’
infixl 6 +

λ :info *
type Num :: * -> Constraint
class Num a where
  ...
  (*) :: a -> a -> a
  ...
        -- Defined in ‘GHC.Num’
infixl 7 *

Так, например, поскольку + — это infixl 6, а * — это infixl 7, если сложение типа 1 + 2 является операндом умножения типа _ * 3, то сложение типа (1 + 2) * 3 должно быть заключено в круглые скобки, потому что 1 + 2 * 3 будет означать что-то другое.

Аналогично, поскольку + есть infixl, выражение 5 + 6 должно заключаться в круглые скобки, когда оно является дочерним элементом 4 + _, что дает 4 + (5 + 6), но не должно, когда оно появляется как дочерний элемент _ + 7, потому что 5 + 6 + 7 = (5 + 6) + 7.

Учитывая этот тип:

data Exp x
  = Abs x (Exp x)
  | App (Exp x) (Exp x)
  | Var x

Экземпляр Show может выглядеть так.

instance (Show x) => Show (Exp x) where
  showsPrec prec exp0 = case exp0 of
    Abs var exp ->
      showParen 
        (prec > appPrec)
        (showString "\\" .
          shows var .
          showString ". " .
          shows exp)
    App exp1 exp2 ->
      showParen 
        (prec > appPrec)
        (showsPrec appPrec exp1 .
          showString " " .
          showsPrec (appPrec + 1) exp2)
    Var var ->
      shows var
    where
      appPrec = 10

Мы можем проверить это вот так.

λ newtype Name = Name Char
λ instance Show Name where show (Name c) = [c]
λ let { f = Name 'f'; x = Name 'x' } in print (Abs f (Abs x (App (Var f) (App (Var f) (Var x)))))
\f. \x. f (f x)

Учитывая все вышесказанное, Show на самом деле не является подходящей абстракцией для этого. (Если вы знакомы с Python, show в Haskell должен выполнять ту же функцию, что и __repr__ в Python, а не __str__.) Show должен быть инструментом отладки, который показывает вам, как именно создается значение, а не просто печатает его в способ скрыть информацию. Я могу обещать, что вы не пожалеете, что написали deriving stock (Show) и использовали другую абстракцию для красивой печати.

Однако какую абстракцию следует использовать? Популярным выбором является пакет Prettyprinter , который включает в себя класс Pretty.

class Pretty a where
  pretty :: a -> Doc ann
  default pretty :: Show a => a -> Doc ann
  pretty = viaShow

Но здесь нет встроенного способа обработки приоритета, и мы не можем добавить аргумент к методу класса pretty. В подобных случаях я предпочитаю добавлять тип-оболочку.

data WithPrec a = WithPrec Int a

Затем мы можем создать экземпляр для типа-оболочки и просто вызывать его из соответствующего экземпляра.

instance (Pretty x) => Pretty (Exp x) where
  pretty = pretty . WithPrec 0

instance (Pretty x) => Pretty (WithPrec (Exp x)) where
  pretty (WithPrec prec exp0) = case exp0 of
    Abs var exp ->
      prettyParen 
        (prec > appPrec)
        ("\\" <>
          pretty var <>
          "." <+>
          pretty exp)
    App exp1 exp2 ->
      prettyParen 
        (prec > appPrec)
        (pretty (WithPrec appPrec exp1) <+>
          pretty (WithPrec (appPrec + 1) exp2))
    Var var ->
      pretty var
    where
      appPrec = 10

prettyParen :: Bool -> Doc a -> Doc a
prettyParen True x = parens x
prettyParen False x = x

Помимо информации о приоритете, такой как WithPrec, в типах-оболочках можно хранить и другие виды контекста. Для операторов вы можете включить ассоциативность, чтобы в некоторых случаях сохранять круглые скобки. В общем, это может быть любая информация о стиле, которую вы хотите использовать во время форматирования, и этот вид контекстуальности можно абстрагировать с помощью комонады Env, если хотите.

Теперь вы можете иметь как симпатичную печать, так и производную Show.

λ print (Abs "f" (Abs "x" (App (Var "f") (App (Var "f") (Var "x")))))
Abs "f" (Abs "x" (App (Var "f") (App (Var "f") (Var "x"))))

λ print (pretty (Abs "f" (Abs "x" (App (Var "f") (App (Var "f") (Var "x"))))))
\f. \x. f (f x)