उन फ़ील्ड को कैसे जोड़ें जो केवल एडीटी को कुछ कैश करते हैं?

Question

अक्सर मुझे एडीटी में फ़ील्ड जोड़ने की आवश्यकता होती है जो केवल कुछ अनावश्यक जानकारी को याद करती है। लेकिन मैंने पूरी तरह से यह समझ नहीं लिया है कि इसे अच्छी तरह से और कुशलता से कैसे किया जाए।

समस्या दिखाने का सबसे अच्छा तरीका उदाहरण बनाना है। मान लीजिए कि हमें untyped लैम्ब्डा शर्तों से काम कर रहे हैं:

type VSym = String 

data Lambda = Var VSym 
      | App Lambda Lambda 
      | Abs VSym Lambda 

और समय-समय पर हम एक शब्दावली से चर के सेट की गणना करने की जरूरत है:

fv :: Lambda -> Set VSym 
fv (Var v) = Set.singleton v 
fv (App s t) = (fv s) `Set.union` (fv t) 
fv (Abs v t) = v `Set.delete` (fv t) 

जल्द ही हम महसूस करते हैं कि fv के बार-बार संगणना हमारे आवेदन की एक बाधा है। हम इसे किसी भी प्रकार डेटा प्रकार में जोड़ना चाहते हैं। पसंद:

data Lambda1 = Var (Set VSym) VSym 
      | App (Set VSym) Lambda Lambda 
      | Abs (Set VSym) VSym Lambda 

लेकिन यह परिभाषा काफी बदसूरत बनाता है। लगभग (Set VSym) बाकी सभी की तुलना में अधिक जगह लेता है। इसके अलावा, यह Lambda का उपयोग करने वाले सभी कार्यों में पैटर्न मिलान को तोड़ देता है। और चीजों को और खराब करने के लिए, अगर हम बाद में कुछ अन्य यादगार क्षेत्र जोड़ने का फैसला करते हैं, तो हमें फिर से सभी पैटर्न फिर से लिखना होगा।

ऐसे सामान्य समाधान को कैसे डिजाइन किया जाए जो ऐसे ज्ञापन फ़ील्ड को आसानी से और अविभाज्य रूप से जोड़ने की अनुमति देता है? मैं निम्नलिखित लक्ष्यों तक पहुंचने के लिए करना चाहते हैं:

1. data परिभाषा, मूल करने के लिए अधिक से अधिक निकट दिखना चाहिए इतना है कि यह आसानी से पढ़ने योग्य और समझा जा सकता है।
2. पैटर्न मैचों को भी सरल और पठनीय रहना चाहिए।
3. बाद में एक नया memoizing क्षेत्र जोड़ने से मौजूदा कोड, विशेष रूप से नहीं तोड़ चाहिए:
   • मौजूदा पैटर्न को तोड़ने के लिए नहीं,
   • परिवर्तन जहां समारोह हम memoize करना चाहते हैं कोड का उपयोग किया जाता है जैसे इस्तेमाल किया गया था (की आवश्यकता नहीं इस उदाहरण में fv)।

---

मैं अपने वर्तमान समाधान व्याख्या करेंगे: data परिभाषा रखने के लिए और पैटर्न यथासंभव कम अव्यवस्था से मेल खाता है, चलो निर्दिष्ट कर सकते हैं:

data Lambda' memo = Var memo VSym 
        | App memo (Lambda' memo) (Lambda' memo) 
        | Abs memo VSym (Lambda' memo) 
type Lambda = Lambda' LambdaMemo 

जहां memoized जा करने के लिए डेटा अलग से परिभाषित किया गया है:

data LambdaMemo = LambdaMemo { _fv :: Set VSym, _depth :: Int } 

फिर के रूप में नकली भाग जो ज्ञापन भाग को पुनर्प्राप्त करता है:

memo :: Lambda' memo -> memo 
memo (Var c _) = c 
memo (App c _ _) = c 
memo (Abs c _ _) = c 

(इसे नामित फ़ील्ड का उपयोग करके समाप्त किया जा सकता है। लेकिन फिर हम have to name all the other fields भी करेंगे।)

यह memoize से विशिष्ट भागों लेने के लिए अनुमति देता है, के रूप में पहले fv का एक ही हस्ताक्षर रखने:

var :: VSym -> Lambda 
var v = Var (LambdaMemo (Set.singleton v) 0) v 

app :: Lambda -> Lambda -> Lambda 
app s t = App (LambdaMemo (fv s `Set.union` fv t) (max (depth t) (depth s))) s t 

abs :: VSym -> Lambda -> Lambda 
abs v t = Abs (LambdaMemo (v `Set.delete` fv t) (1 + depth t)) v t 

अब हम कर सकते हैं:

fv :: Lambda -> Set VSym 
fv = _fv . memo 

depth :: Lambda -> Int 
depth = _depth . memo 

अंत में, हम इन स्मार्ट कंस्ट्रक्टर्स घोषित

canSubstitute :: VSym -> Lambda -> Lambda -> Bool 
canSubstitute x s t 
    | not (x `Set.member` (fv t)) 
     = True -- the variable doesn't occur in `t` at all 
canSubstitute x s t@(Abs _ u t') 
    | u `Set.member` (fv s) 
     = False 
    | otherwise 
     = canSubstitute x s t' 
canSubstitute x s (Var _ _) 
     = True 
canSubstitute x s (App _ t1 t2) 
     = canSubstitute x s t1 && canSubstitute x s t2 

जैसे ज्ञात फ़ील्ड पढ़ने के साथ पैटर्न मिलान को कुशलता से लिखें

यह हल करने लगता है:

• पैटर्न मिलान अभी भी काफी उचित है।
• यदि हम एक नया ज्ञापन फ़ील्ड जोड़ते हैं तो यह मौजूदा कोड को बाधित नहीं करेगा।
• यदि हम हस्ताक्षर Lambda -> Something के साथ फ़ंक्शन को याद करने का निर्णय लेते हैं तो हम इसे आसानी से नए ज्ञापन फ़ील्ड के रूप में जोड़ सकते हैं।

क्या मैं अभी भी इस डिजाइन के बारे में पसंद नहीं है:

• data परिभाषा इतना बुरा नहीं है, लेकिन अभी भी हर जगह memo रखने clutters यह काफी।
• हमें मूल्य बनाने के लिए स्मार्ट कन्स्ट्रक्टर की आवश्यकता है लेकिन हम पैटर्न मिलान के लिए नियमित रचनाकारों का उपयोग करते हैं। यह इतना बुरा नहीं है, हम बस एक _ जोड़ते हैं, लेकिन निर्माण और deconstructing के लिए एक ही हस्ताक्षर होने अच्छा होगा। मुझे लगता है कि Views या Pattern Synonyms इसे हल करेगा।
• ज्ञापन फ़ील्ड (मुक्त चर, गहराई) की गणना स्मार्ट कन्स्ट्रक्टरों के साथ कसकर मिलती है। चूंकि यह मानना ​​उचित है कि उन ज्ञापन कार्यों को हमेशा catamorphisms होगा, मेरा मानना ​​है कि इसे the fixpoint package जैसे टूल द्वारा हल किया जा सकता है।

कोई भी विचार है कि यह कैसे सुधार करने के लिए? या ऐसी समस्या को हल करने के बेहतर तरीके हैं?

Answer 1

मैं अपने लक्ष्यों के सभी समारोह में के बजाय एडीटी अपने आप में परिणाम कैशिंग द्वारा सादे पुराने Memoization का उपयोग करके पूरा किया जा सकता है। बस कुछ हफ्ते पहले, मैंने stable-memo पैकेज जारी किया, जिसे यहां सहायता करनी चाहिए। अपने मानदंडों की जांच करते हुए, मुझे नहीं लगता कि हम इससे बेहतर कुछ कर सकते हैं:

1. आपकी डेटा परिभाषा बिल्कुल नहीं बदली है।
2. पैटर्न मिलान नहीं बदलता है, या तो।
3. मौजूदा कोड को केवल इसलिए बदलना नहीं है क्योंकि आप अधिक ज्ञापन कार्यों को लिखते हैं।
   • कोई मौजूदा पैटर्न टूटा नहीं है।
   • कोई मौजूदा ज्ञापन कार्य टूटा नहीं है।

का उपयोग करते हुए यह बहुत सरल है। बस किसी भी फ़ंक्शन को memo लागू करें जिसे आप याद रखना चाहते हैं, यह सुनिश्चित कर लें कि आप रिकर्सिव कॉल में भी हर जगह फ़ंक्शन के ज्ञापन संस्करण का उपयोग करें।यहाँ कैसे उदाहरण आप अपने प्रश्न में इस्तेमाल लिखने के लिए है:

import Data.StableMemo 

type VSym = String 

data Lambda = Var VSym 
      | App Lambda Lambda 
      | Abs VSym Lambda 

fv :: Lambda -> Set VSym 
fv = memo go 
    where 
    go (Var v) = Set.singleton v 
    go (App s t) = fv s `Set.union` fv t 
    go (Abs v t) = v `Set.delete` fv t