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

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, чтобы комбинировать «субтермы» и «подрезультаты» способами, которые невозможно с помощью Складной.

Мой вопрос: могу ли я построить 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