一个递归方案的库实现

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。因此，我添加了一个连接函数：

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？

- nponeccop

---

参考：https://dev59.com/QGYr5IYBdhLWcg3w4-B-。 - Will Ness

Answer 1

将函数折叠成“吃掉参数并保留它”的形式称为参面变换。事实上，您的函数可以使用递归模式轻松表示为：

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

此外，如果我们像您在processTerm中所做的那样向cataWithSubterm提供(,)，我们将得到

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

这正是专门针对Fix而制定的para：

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

- Petr