एक रिकर्सन योजना

Question

का एक लाइब्रेरी कार्यान्वयन मैंने 'एक आविष्कार योजना' का आविष्कार किया जो कि कैटमोर्फिज्म का सामान्यीकरण है। जब आप catamorphism के साथ एक डेटा संरचना गुना आप केवल तह के subresults को, subterms के लिए उपयोग नहीं है:

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

तह समारोह phiself 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 की एक व्युत्पन्न उदाहरण का उपयोग करते हुए एक सरल कार्यान्वयन के अस्तित्व की उम्मीद है। लेकिन आम तौर पर यह मामला नहीं है क्योंकि phiExampleFunctor की आंतरिक संरचना के ज्ञान को 'सबटरम्स' और 'सब्रेसल्ट्स' को फोल्ड करने योग्य तरीके से गठबंधन करने के लिए लागू कर सकता है।

मेरा प्रश्न है: क्या मैं को 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 

मिलता जो ठीक paraFix के लिए विशेष है:

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