haskell - recursivas - ¿Es posible comparar dos árboles con esquemas de recursión?

listas recursivas en haskell

Question

Tengo este AST

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

y quiero comparar

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

Pero todas las funciones de esquemas de recursión parecen funcionar solo con una sola estructura

Obviamente puedo usar recursión

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

Pero espero que sea posible utilizar algún tipo de función de cierre automático.

Answer 1

Los esquemas de recursión que actúan en un único argumento son suficientes, porque podemos devolver una función desde una aplicación de esquema. En este caso, podemos devolver una función Expr -> Bool desde una aplicación de esquema en Expr . Para una comprobación de igualdad eficiente, solo necesitamos paramorfismos:

{-# 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

Por supuesto, cata es trivialmente aplicable en términos de para :

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

Técnicamente, casi todas las funciones útiles son implementables usando cata , pero no son necesariamente eficientes. Podemos implementar para usar cata :

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

Sin embargo, si usamos para'' en eqExpr obtenemos complejidad cuadrática, ya que para'' siempre es lineal en el tamaño de la entrada, mientras que podemos usar para para Expr valores Expr más altos en tiempo constante.

Answer 2

(Esta respuesta usa la biblioteca de corrección de datos porque no pude compilar los esquemas de recursión ).

Podemos modelar la diferencia de dos árboles como un anamorfismo o despliegue de un "functor de diferencias" que se basa en el functor original.

Considera los siguientes tipos

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

type ExprDiff = Fix (DiffF ExprF) 

La idea es que ExprDiff seguirá la "estructura común" de los árboles Expr originales, siempre y cuando se mantenga igual, pero en el momento en que se encuentra una diferencia, cambiamos a la hoja Diff , que almacena los dos subárboles que encontramos ser diferente.

La función de comparación real sería:

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

La "semilla" del anamorfismo es el par de expresiones que queremos comparar.

Si simplemente queremos un predicado Expr -> Expr -> Bool podemos usar un catamorfismo que detecta la presencia de ramas Diff .