मान लीजिए कि मैं इस तरह के रूप में एक scott-encoded सूची है:क्या कोई गैर-रिकर्सिव शब्द है जो स्कॉट-एन्कोडेड सूची में फोल्ड करता है?
scott = (\ c n -> c 1 (\ c n -> c 2 (\ c n -> c 3 (\ c n -> n))))
मैं एक समारोह है कि सूची इस तरह प्राप्त करता है और एक वास्तविक सूची ([1,2,3]) में बदल देता है, कि इस तरह के समारोह को छोड़कर पुनरावर्ती नहीं किया जा सकता चाहते हैं। यही है, यह ईटा-बीटा सामान्य रूप में होना चाहिए। क्या यह कार्य मौजूद है?
ठीक है, मैं इसे एक शॉट देता हूं। मुझे सही करने के लिए स्वतंत्र महसूस करें, क्योंकि मैं इस पर एक विशेषज्ञ नहीं हूं।
मनमाना x और xs के लिए, यह मामला है कि toList (\c n -> c x xs) एक शब्द है कि x : toList xs के लिए परिवर्तनीय है कम कर देता है होना चाहिए।
यह तभी संभव है अगर हम कुछ c और n को (\c n -> c x xs) लगाने से c x xs के बाएं हाथ की ओर कम। तो toList ~ (\f -> f ? ?)। (बीटीडब्लू, यह वह हिस्सा है जहां मैं एक अच्छा कठोर तर्क नहीं सोच सकता था; मेरे पास कुछ विचार थे लेकिन कोई भी अच्छा नहीं था। मुझे सुझाव सुनने में खुशी होगी)।
अब यह मामला होना चाहिए कि c x xs ~ (x : toList xs)। लेकिन x और xs अलग सार्वभौमिक चर हैं, और वे दाएं हाथ में होने वाले एकमात्र चर हैं, समीकरण Miller's pattern fragment में है, और इसलिए c ~ (\x xs -> x : toList xs) इसका सबसे सामान्य समाधान है।
तो, toList के लिए (\f -> f (\x xs -> x : toList xs) n) को कम करना चाहिए। स्पष्ट रूप से, toList का सामान्य रूप नहीं हो सकता है, क्योंकि हम हमेशा रिकर्सिव घटना को प्रकट कर सकते हैं।
मुझे मिलर के पैटर्न खंड भाग नहीं मिलते हैं, लेकिन यह मेरे लिए बहुत सही लग रहा है। – MaiaVictor
अस्वीकरण: मैं (स्पष्ट रूप से) पूरी तरह से सुनिश्चित नहीं हूं कि यह सही है। – MaiaVictor
उस विशिष्ट सूची के लिए, हाँ यह मौजूद है। लेकिन आप निश्चित रूप से एक ऐसा फ़ंक्शन का अर्थ लेते हैं जो _any_ ऐसी सूची ले सकता है, मनमाने ढंग से लंबा, और एक मानक सूची देता है, है ना? – chi
हां, यही मेरा मतलब है। – MaiaVictor
यह सूची के अंत में '\ c n -> c 3 (\ c n -> n) नहीं होना चाहिए? –