haskell - 递归方案的库实现

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 无法实现的方式组合“子项”和“子结果”。

我的问题是:我可以建立 processTerm使用现代递归方案库中的常用函数，例如 recursion-schemes/Data.Functor.Foldable ?

Answer 1

折叠使得它“吃掉论点并保留它”被称为 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