haskell - 是否可以用递归方案比较两棵树？

Question

我有这个 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

但我希望可以使用某种 zipfold 功能。

Answer 1

作用于单个参数的递归方案就足够了，因为我们可以从方案应用程序返回一个函数。在这种情况下，我们可以从 Expr 上的方案应用程序返回一个 Expr -> Bool 函数。为了有效地进行相等性检查，我们只需要拟态:

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

但是，如果我们在 eqExpr 中使用 para'，我们会得到二次复杂度，因为 para' 始终与输入大小呈线性关系，而我们可以使用 para 在常数时间内查看最上面的 Expr 值。