问题 递归方案的库实现


我发明了一种递归方案,这种方法是对同态性的推广。折叠具有catamorphism的数据结构时,您无法访问子项,只能访问折叠的子结果:

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


8146
2017-08-02 09:36


起源

比照 stackoverflow.com/questions/13317242/what-are-paramorphisms。 - Will Ness


答案:


折叠使得它“吃掉论证并保持它”也被称为a paramorphism。实际上,您的功能可以很容易地表达出来 递归的方案 如

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

12
2017-08-02 11:33