Biblioteczna implementacja schematu rekursji

Question

"Wymyśliłem" program rekursji, który jest uogólnieniem katamorfizmu. Kiedy złożyć strukturę danych z catamorphism nie masz dostępu do subterms, tylko subresults składanych:

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

Funkcja składane phi ma tylko dostęp do wyniku self x, ale nie do oryginalnego x. Więc dodałem łączący funkcję:

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 

Teraz to możliwe łączenie x i self x w sensowny sposób, na przykład za pomocą (,):

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 powroty dla każdego identyfikatora listę rzeczywistych argumentów to otrzymuje na różnych ścieżkach kontrolnych. Na przykład. dla bar (foo 2) (foo 5) powraca fromList [("foo", [2, 5])]

Należy zauważyć, że w tym przypadku wyniki są połączone jednolicie z innych wyników, więc spodziewać się istnienia prostszą realizację pomocą instancji pochodny Data.Foldable. Ale ogólnie nie jest tak, ponieważ phi może zastosować swoją wiedzę o wewnętrznej strukturze ExampleFunctor, aby łączyć "subterms" i "subresults" w sposób niemożliwy z Foldable.

Moje pytanie brzmi: czy mogę zbudować processTerm używając funkcji czasowych z nowoczesnej biblioteki schematów rekursji, takich jak recursion-schemes/Data.Functor.Foldable?

Answer 1

Składanie w taki sposób, że "zjada argument i utrzymuje go" nazywa się paramorphism. Rzeczywiście, czynność można łatwo wyrazić za pomocą recursion-schemes jak

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

Ponadto, jeśli dostarczamy (,) do cataWithSubterm jak to było w processTerm otrzymujemy

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

który właśnie para specjalizuje Fix:

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