Kann man zwei Bäume mit Rekursionschemata vergleichen?

Question

Ich habe diesen AST

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

und ich mag

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

Aber alle Rekursion Systeme Funktionen scheinen vergleichen nur mit einzelner Struktur

Offensichtlich ich Rekursion

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 

verwenden kann, arbeiten

Aber ich hoffe, es ist möglich, s zu verwenden eine Art Zipfold-Funktion.

Answer 1

Rekursionschemata, die auf ein einzelnes Argument einwirken, reichen aus, da wir eine Funktion aus einer Schemaanwendung zurückgeben können. In diesem Fall können wir eine Expr -> Bool Funktion von einer Schemaanwendung auf Expr zurückgeben. Für eine effiziente Gleichheit Kontrolle brauchen wir nur 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 

Natürlich cata ist trivialer implementierbar in Bezug auf para:

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

Technisch fast alle nützlichen Funktionen implementierbar sind mit cata, aber sie aren‘ t unbedingt effizient. Wir können paracata mit implementieren:

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

Wenn wir jedoch para' in eqExpr verwenden wir quadratische Komplexität erhalten, da para' immer in der Größe des Eingangs linear, während wir para können an den obersten Expr spähen Werte in konstanter Zeit.

Answer 2

(Diese Antwort verwendet die Daten-fix Bibliothek, weil ich nicht Rekursion-Systeme zu kompilieren. Bekommen konnte)

Wir können modellieren die diff von zwei Bäumen als Anamorphismus oder Entfaltung eines " Diff Funktor ", der auf dem ursprünglichen Funktor basiert.

Betrachten Sie die folgenden Arten

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

type ExprDiff = Fix (DiffF ExprF) 

Die Idee ist, dass ExprDiff die „gemeinsame Struktur“ der ursprünglichen Expr Bäume folgen, solange sie gleich bleibt, aber im Moment ein Unterschied auftritt, wir wechseln zum Diff Blatt, das die zwei Teilbäume speichert, die wir anders fanden.

Die tatsächliche Vergleichsfunktion wäre:

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 

Der „Samen“ des Anamorphismus ist das Paar von Ausdrücken wir vergleichen wollen.

Wenn wir einfach ein Prädikat Expr -> Expr -> Bool wollen, können wir später einen Katamorphismus verwenden, der das Vorhandensein von Diff Verzweigungen erkennt.