有沒有像cata的東西，但你可以匹配內部結構？

Question

我有這樣的語言AST

data ExprF r = Const Int 
       | Var String 
       | Lambda String r 
       | EList [r] 
       | Apply r r 
deriving (Show, Eq, Ord, Functor, Foldable) 

我想將它轉換爲字符串

toString = 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, ")"] 

但是，當拉姆達在Apply使用我所需要的括號

(x => x)(1) 

，但我不能匹配cata的內部結構

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

有沒有比para更好的解決方案？

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, ")"] 

它看起來更醜。即使它只需要在一個地方，我需要刪除fst元組參數，我想它會變慢。

Answer 1

正如@chi，@DanielWagner和我在評論中指出的那樣，以結構遞歸的方式做這種漂亮的印刷和圓括號的方式是「showsPrec方法」。

大的想法是不把語法樹摺疊成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的參數。然後，在Lambda的情況下，我們檢查這個論點。如果當前的術語是應用程序的左邊部分，我們用lambert表示;如果不是，我們不會。

在頂層，將整棵樹摺疊成一個函數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" 

通過用Int替換Bool，這種方法可以被概括任意優先級到parenthesising運營商，如覆蓋@DanielWagner's linked answer。

Answer 2

如何直遞歸缺少的情況：

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 

Answer 3

一種解決方案是使用{-# 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編譯，我無法說服窮舉檢查匹配模式上都面面俱到。