再帰スキームのライブラリ実装

Question

異教徒の一般化である再帰スキームを「発明しました」。

{-# LANGUAGE DeriveFunctor #-} 
import qualified Data.Map as M 

newtype Fix f = Fix { unFix :: f (Fix f) } 

cata :: Functor f => (f b -> b) -> Fix f -> b 
cata phi = self where 
    self = phi . fmap (\x -> self x) . unFix 

折りたたみ機能phiがself xの結果へのアクセスのみを持っている、ではなく、元のxへ：あなたはcatamorphismとデータ構造を折るときにあなただけの折りたたみのsubresultsに、部分項にアクセスすることはできません。だから私は、参加機能を追加しました：

cataWithSubterm :: Functor f => (Fix f -> c -> b) -> (f b -> c) -> Fix f -> c 
cataWithSubterm join phi = self 
    where self = phi . fmap (\x -> join x (self x)) . unFix 

今では(,)を使用して、たとえば、有意義な方法でxとself xを組み合わせることが可能です：

data ExampleFunctor a = Var String | Application a a deriving Functor 

type Subterm = Fix ExampleFunctor 

type Result = M.Map String [Subterm] 

varArgs :: ExampleFunctor (Subterm, Result) -> Result 
varArgs a = case a of 
    Var _ -> M.empty 
    Application ((Fix (Var var)), _) (arg, m) -> M.insertWith (++) var [arg] m 

processTerm :: (ExampleFunctor (Subterm, Result) -> Result) -> Subterm -> Result 
processTerm phi term = cataWithSubterm (,) phi term  

processTerm varArgsリターンを各識別子の実際の引数のリストをそれ異なる制御経路で受信する。例えば。 bar (foo 2) (foo 5)のためには、この例では結果を他の結果と均一に結合されることfromList [("foo", [2, 5])]

注意を返すので、私は、Data.Foldableの派生インスタンスを使用して、簡単な実装が存在することを期待します。しかし、一般的には、phiは、ExampleFunctorの内部構造に関する知識を適用して、Foldableでは不可能な方法で 'サブターム'と 'サブサブルス'を組み合わせることができます。

私の質問はrecursion-schemes/Data.Functor.Foldableのような最新の再帰スキームライブラリのストック機能を使用してprocessTermをビルドできますか？

Answer 1

「引数を取ってそれを保持する」という折りたたみは、paramorphismと呼ばれます。我々はcataWithSubtermに(,)を供給する場合は、processTermで行ったように確かに、あなたの関数を容易に、

cataWithSubterm :: Functor f => (Fix f -> b -> a) -> (f a -> b) -> Fix f -> b 
cataWithSubterm f g = para $ g . fmap (uncurry f) 

またrecursion-schemes

として使用して表現することができ、我々は正確に Fixに特化 paraある

cataWithSubterm (,) :: Functor f => (f (Fix f, b) -> b) -> Fix f -> b 

を得る：

para     :: Functor f => (f (Fix f, b) -> b) -> Fix f -> b