Есть ли что-то вроде ката, но где вы можете сопоставить внутреннюю структуру?

Как @chi, @DanielWagner и я указали в комментариях, способ сделать такого рода красивую печать с круглыми скобками структурно рекурсивным способом - это "_ 1_ подход".

Основная идея состоит не в том, чтобы сворачивать синтаксическое дерево в String, а в функцию Bool -> String. Это дает нам определенную степень чувствительности к контексту в свертке: мы будем использовать этот дополнительный параметр Bool, чтобы отслеживать, находимся ли мы в настоящее время в контексте левой части приложения.

parens x = "(" ++ x ++ ")"

ppAlg :: ExprF (Bool -> String) -> (Bool -> String)
ppAlg (Const x) isBeingApplied = show x
ppAlg (Var x) isBeingApplied = x
ppAlg (Lambda name body) isBeingApplied = p ("\\" ++ name ++ " -> " ++ body False)
    where p = if isBeingApplied then parens else id
ppAlg (EList es) isBeingApplied = unwords (sequenceA es False)
ppAlg (Apply fun arg) isBeingApplied = fun True ++ " " ++ arg False

Мы передаем значения isBeingApplied по рекурсивным вызовам в зависимости от того, где мы находимся в синтаксическом дереве прямо сейчас. Обратите внимание, что единственное место, где мы передаем True, - это аргумент fun в теле дела Apply. Затем, в случае Lambda, мы проверяем этот аргумент. Если текущий термин является левой частью приложения, мы заключаем лямбда в скобки; если нет, то нет.

На верхнем уровне, свернув все дерево в функцию Bool -> String, мы передаем ей аргумент False - в настоящее время мы не находимся в контексте приложения - чтобы получить String.

pp :: Expr -> String
pp ex = cata ppAlg ex False

ghci> pp $ app (lam "x" (var "x")) (cnst 2)
"(\\x -> x) 2"

Заменив Bool на Int, этот подход можно обобщить на операторы в скобках с произвольным приоритетом, как описано в Связанный ответ @ DanielWagner.

Одним из решений является использование расширения {-# LANGUAGE PatternSynonyms #-} и определение однонаправленных шаблонов, например:

pattern Apply' r1 r2 <- Apply (_,r1) (_,r2)

которые вы затем можете использовать в своих определениях следующим образом:

toString2 :: Fix ExprF -> String
toString2 = para $ \case
  Const x -> show x
  Var x -> x
  Lambda x (_,y) -> unwords [x, "=>", y]
  EList x -> unwords (snd <$> x)
  Apply ((Fix Lambda {}),x) (_,y) -> unwords ["(", x, ")", "(", y, ")"]
  Apply' x y -> unwords [x, "(", y, ")"]

Поскольку ExprF является функтором, другим вариантом будет просто написать:

toString2' :: Fix ExprF -> String
toString2' = para $ \case
  Apply ((Fix Lambda {}),x) (_,y) -> unwords ["(", x, ")", "(", y, ")"]
  other -> case fmap snd other of
      Const x -> show x
      Var x -> x
      Lambda x y -> unwords [x, "=>", y]
      Apply x y -> unwords [x, "(", y, ")"]

С синонимом шаблона и компиляцией с -Wall мне трудно убедить средство проверки полноты, что совпадения с шаблоном являются исчерпывающими.

Как насчет прямой рекурсии для отсутствующего случая:

toString :: Fix ExprF -> String
toString (Fix (Apply (Fix (Lambda _ x)) y)) = "(" ++ toString x ++ ")(" ++ toString y ++ ")"
toString z = (cata $ \case
  Const x -> show x
  Var x -> x
  EList x -> unwords x
  Lambda x y -> unwords [x, "=>", y]
  Apply x y -> unwords [x, "(", y, ")"]) z