11

私はこの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機能を使用できることを願っています。

4

2 に答える 2

6

スキーム アプリケーションから関数を返すことができるため、単一の引数に作用する再帰スキームで十分です。この場合、Expr -> Bool上のスキーム アプリケーションから関数を返すことができますExpr。効率的な等価性チェックには、パラモーフィズムのみが必要です。

{-# 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できますが、必ずしも効率的であるとは限りません。para以下を使用して実装できますcata。

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

ただし、para'inを使用すると、入力のサイズが常に線形であるeqExprため、2 次の複雑さが得られますが、 を使用して、一定時間で最上位の値を覗くことができます。para'paraExpr

于 2016-07-23T16:15:59.513 に答える