是否有可能使用遞歸方案比較兩棵樹？

我有這個AST是否有可能使用遞歸方案比較兩棵樹？

data ExprF r = Const Int | Add r r 
type Expr = Fix ExprF

，我想比較

x = Fix $ Add (Fix (Const 1)) (Fix (Const 1)) 
y = Fix $ Add (Fix (Const 1)) (Fix (Const 2))

但是所有的遞歸方案的功能似乎只用單一結構

顯然工作，我可以用遞歸

eq (Fix (Const x)) (Fix (Const y)) = x == y 
eq (Fix (Add x1 y1)) (Fix (Add x2 y2)) = (eq x1 x2) && (eq y1 y2) 
eq _ _ = False

但我希望有可能使用s有些拉鍊功能。

來源

2016-07-23 ais

從哪裏得到您的Fix？ – danidiaz

https：// hackage。haskell.org/package/recursion-schemes – ais

你可能想要一個zygohistomorphic prepromorphism。我不知道它做了什麼，但有了這樣的名字，我無法想象它有多少*不能做。 :) – chepner

作用於單個參數的遞歸方案就夠了，因爲我們可以從方案應用程序返回一個函數。在這種情況下，我們可以從Expr上的方案應用程序返回Expr -> Bool函數。爲了有效地平等檢查，我們只需要paramorphisms：

{-# language DeriveFunctor, LambdaCase #-} 

newtype Fix f = Fix (f (Fix f)) 
data ExprF r = Const Int | Add r r deriving (Functor, Show) 
type Expr = Fix ExprF 

cata :: Functor f => (f a -> a) -> Fix f -> a 
cata f = go where go (Fix ff) = f (go <$> ff) 

para :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a 
para f (Fix ff) = f ((\x -> (x, para f x)) <$> ff) 

eqExpr :: Expr -> Expr -> Bool 
eqExpr = cata $ \case 
    Const i -> cata $ \case 
    Const i' -> i == i' 
    _  -> False 
    Add a b -> para $ \case 
    Add a' b' -> a (fst a') && b (fst b') 
    _   -> False

當然，cata是在para方面平凡實現的：

cata' :: Functor f => (f a -> a) -> Fix f -> a 
cata' f = para (\ffa -> f (snd <$> ffa)

從技術上講，幾乎所有有用的功能是可實現使用cata，但他們不是活得不一定高效。我們可以通過cata實現para：

para' :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a 
para' f = snd . cata (\ffa -> (Fix (fst <$> ffa) , f ffa))

但是，如果我們用para'在eqExpr我們得到二次複雜，因爲para'總是在輸入的大小呈線性關係，而我們可以用para在最上面的Expr偷看值在不變的時間。

來源

2016-07-23 16:15:59

是否可以像'cataZipWith :: Fix f - > Fix f - >（f a - > f c - > a） - > a'那樣編寫'eqExpr'的多態版本？ – ais

@AndrásKovács在執行'eqExpr'時，爲什麼模式匹配背後的catas/paras是必需的？我們不能在第二棵樹上直接模式匹配嗎？ – danidiaz

@danidiaz我認爲我們只能使用遞歸方案。 –

（此反應使用數據修復庫，因爲我無法得到遞歸的方案編譯。）

我們可以兩棵樹的差異模型作爲anamorphism或的展開「差異仿函數「，它是基於原函子的。

考慮以下類型

data DiffF func r = Diff (Fix func) (Fix func) 
        | Nodiff (func r) 
        deriving (Functor) 

type ExprDiff = Fix (DiffF ExprF)

的想法是，ExprDiff將按照原Expr樹的「共同結構」，只要它保持平等的，但在遇到差的那一刻，我們切換到Diff葉，它存儲我們發現不同的兩個子樹。

實際比較函數是：

diffExpr :: Expr -> Expr -> ExprDiff 
diffExpr e1 e2 = ana comparison (e1,e2) 
    where 
    comparison :: (Expr,Expr) -> DiffF ExprF (Expr,Expr) 
    comparison (Fix (Const i),Fix (Const i')) | i == i' = 
     Nodiff (Const i') 
    comparison (Fix (Add a1 a2),Fix (Add a1' a2')) = 
     Nodiff (Add (a1,a1') (a2,a2')) 
    comparison (something, otherthing) = 
     Diff something otherthing

的的anamorphism的「種子」是對我們要比較的表達式。

如果我們只是想要一個謂詞Expr -> Expr -> Bool，我們可以稍後使用一個變形檢測Diff分支的存在。

來源

2016-07-24 10:35:41 danidiaz

是否有可能使用遞歸方案比較兩棵樹？

回答

相關問題