रिकर्सन योजनाओं का उपयोग कर एल्गोरिदम डब्ल्यू

Question

मैं फिक्स-पॉइंट डेटा प्रकारों और रिकर्सन स्कीम का उपयोग करके हिंडली-मिलनर प्रकार अनुमान एल्गोरिदम बनाने में सक्षम होना चाहता था। वास्तविक प्रत्यावर्तन भागों से अलग सभी विस्तार की अनदेखी:

w env term = case term of 
    Lam n e -> lam (w (modify1 env) e) 
    App a b -> app (w (modify2 env) a) (w (modify3 env) b) 
    ... 

एल्गोरिथ्म एक वातावरण डेटा संरचना बनाता env के रूप में यह पुनरावर्ती पेड़ को पार करता है जब तक यह लीफ़्स तक पहुँचता है। फिर यह इस जानकारी का उपयोग करता है क्योंकि यह परिणाम फिर से बनाता है।

env भाग के बिना, इसे cata के साथ आसानी से कार्यान्वित किया जा सकता है। क्या यह (env के साथ) सामान्य रूप से रिकर्सन योजनाओं का उपयोग करके किया जा सकता है?

Answer 1

हाँ बस cata का लक्ष्य एक समारोह Env -> a

बनाने - luqui

हाँ, पर आप शायद एक उच्च क्रम वाहक प्रकार के साथ cata का उपयोग करना होगा, एक ऐसी क्रिया की गणना करना जो पर्यावरण को संशोधित कर सकता है और संभवतः असफल हो सकता है।

- pigworker

Answer 2

env भाग के बिना, यह आसानी से cata साथ लागू किया जा सकता है। क्या यह (एनवी के साथ) सामान्य रूप से रिकर्सन योजनाओं का उपयोग कर किया जा सकता है?

जो आप खोज रहे हैं वह chronomorphism है। यह आपको भविष्य में और अतीत से परिणामों का उपयोग करके रिकर्सन करने की अनुमति देता है। यह उपयोगकर्ता के अनुकूल के रूप में काफी नहीं है, लेकिन यह रिकर्सन योजनाओं का उपयोग करके चीजों को करने का वैचारिक तरीका है।