Eine Bibliotheksimplementierung eines Rekursionsschemas

Question

Ich 'erfand' ein Rekursionsschema, das eine Verallgemeinerung des Katamorphismus ist. Wenn Sie eine Datenstruktur mit catamorphism falten Sie haben keinen Zugang zu Termen, nur Nebenergebnisse der Faltung:

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

Die Klappfunktion phi nur Zugriff auf das Ergebnis von self x hat, aber nicht zu den ursprünglichen x. So habe ich eine Verbindungsfunktion:

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 

Jetzt ist es möglich x und self x in einer sinnvollen Art und Weise zu kombinieren, zum Beispiel (,) mit:

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 kehrt für jede Kennung, die Liste der tatsächlichen Argumente, die es empfängt auf verschiedenen Kontrollpfaden. Z.B. für bar (foo 2) (foo 5) gibt es fromList [("foo", [2, 5])]

Beachten Sie, dass mit anderen Ergebnissen einheitlich in diesem Beispiel Ergebnisse kombiniert, so dass ich erwarte Existenz einer einfacheren Implementierung eine abgeleitete Instanz Data.Foldable verwenden. Aber im Allgemeinen ist dies nicht der Fall, da phi sein Wissen über die interne Struktur von ExampleFunctor anwenden kann, um "Subterms" und "Subresults" auf eine Weise zu kombinieren, die mit Foldable nicht möglich ist.

Meine Frage ist: kann ich processTerm mit Lagerfunktionen aus einer modernen Rekursionschemata-Bibliothek wie recursion-schemes/Data.Functor.Foldable bauen?

Answer 1

Folding so, dass es "das Argument isst und es auch hält" wird paramorphism genannt. Tatsächlich kann Ihre Funktion leicht ausgedrückt werden unter Verwendung von recursion-schemes als

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

Außerdem, wenn wir (,)-cataWithSubterm liefern, wie Sie in processTerm haben, bekommen wir

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

die genau para für Fix spezialisiert ist:

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