一個遞歸方案的庫實現

我'發明'一個遞推方案，這是一個變形的泛化。當你與catamorphism倍的數據結構，你沒有訪問subterms，只能摺疊子結果：一個遞歸方案的庫實現

{-# 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。所以我加了加入功能：

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的內部結構的知識以「摺疊」不可能的方式組合'子項'和'子結果'。

我的問題是：我可以建立processTerm使用庫存函數從一個現代的遞歸方案庫，如recursion-schemes/Data.Functor.Foldable？

來源

2013-08-02 nponeccop

cf. http://stackoverflow.com/questions/13317242/what-are-paramorphisms。 –

摺疊使其「消化參數並保持它」被稱爲paramorphism。事實上，你的功能可以很容易地表示使用recursion-schemes作爲

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

而且，如果我們提供(,)到cataWithSubterm您在processTerm一樣，我們得到

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

而這恰恰是para專門用於Fix：

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

來源

2013-08-02 11:33:00

一個遞歸方案的庫實現

回答

相關問題