Реализация схемы рекурсии библиотеки

Я придумал схему рекурсии, которая является обобщением катаморфизма. Когда вы складываете структуру данных с катаморфизмом, у вас нет доступа к субтермам, только к подрезультатам складывания:

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

Ответ 1