रैकेट में अजीब तरीके से फोल्ड क्यों परिभाषित किया गया है?

Question

हास्केल में, कई अन्य कार्यात्मक भाषाओं की तरह, फ़ंक्शन foldl इस तरह परिभाषित किया गया है, उदाहरण के लिए, foldl (-) 0 [1,2,3,4] = -10।

यह ठीक है, क्योंकि foldl (-) 0 [1, 2,3,4] परिभाषा के अनुसार, ((((0 - 1) - 2) - 3) - 4) है।

लेकिन, रैकेट में, (foldl - 0 '(1 2 3 4)) 2, क्योंकि रैकेट "समझदारी से" इस तरह की गणना करता है: (4 - (3 - (2 - (1 - 0)))), जो वास्तव में है 2.

बेशक

, अगर हम सहायक समारोह फ्लिप, इस तरह परिभाषित करते हैं:

(define (flip bin-fn) 
    (lambda (x y) 
    (bin-fn y x))) 

तो हम रैकेट में हास्केल में के रूप में ही व्यवहार को प्राप्त कर सकते हैं: (foldl - 0 '(1 2 3 4)) के बजाय हम लिख सकते हैं: (foldl (flip -) 0 '(1 2 3 4))

सवाल यह है: क्यों रैकेट में foldl है इस तरह के एक विषम (गैर मानक और nonintuitive) तरीके से परिभाषित, किसी भी अन्य भाषा की तुलना में अलग?

Answer 1

रैकेट documentation से, foldl का विवरण:

(foldl proc init lst ...+) → any/c 

दो अपने प्रश्न के लिए दिलचस्पी की बात का उल्लेख कर रहे:

इनपुट lsts सही

बाएं से आगे बढ़ते जाते हैं

और

foldl निरंतर अंतरिक्ष में lsts प्रक्रियाओं

मैं कैसे सादगी की खातिर एक भी सूची के साथ कैसा लग सकता है कि के लिए कार्यान्वयन, पर अटकलें कर रहा हूँ:

(define (my-foldl proc init lst) 
    (define (iter lst acc) 
    (if (null? lst) 
     acc 
     (iter (cdr lst) (proc (car lst) acc)))) 
    (iter lst init)) 

आप देख सकते हैं , बाएं से दाएं ट्रैवर्सल और निरंतर स्थान की आवश्यकताओं को पूरा किया जाता है (iter में पूंछ रिकर्सन देखें), लेकिन के लिए तर्कों के आदेश में कभी निर्दिष्ट नहीं किया गया था। इसलिए, उपरोक्त कोड बुला का परिणाम होगा:

(my-foldl - 0 '(1 2 3 4)) 
> 2 

अगर हम इस तरह से proc के लिए तर्कों की क्रम निर्दिष्ट था:

(proc acc (car lst)) 

फिर परिणाम होगा:

(my-foldl - 0 '(1 2 3 4)) 
> -10 

मेरा मुद्दा यह है कि foldl के लिए प्रलेखन proc के लिए तर्कों के मूल्यांकन आदेश पर कोई धारणा नहीं करता है, यह केवल एच यह गारंटी देने के लिए कि निरंतर स्थान का उपयोग किया जाता है और सूची में तत्वों का मूल्यांकन बाएं से दाएं से किया जाता है।

एक तरफ ध्यान दें के रूप में, आप बस इस लिख कर अपने अभिव्यक्ति के लिए वांछित मूल्यांकन आदेश प्राप्त कर सकते हैं:

(- 0 1 2 3 4) 
> -10 

Answer 2

रैकेट के foldl और foldr (और यह भी SRFI-1'sfold और fold-right) संपत्ति है कि

(foldr cons null lst) = lst 
(foldl cons null lst) = (reverse lst) 

मुझे लगता है कि उस कारण के लिए तर्क आदेश चुना गया था।

Answer 3

• हास्केल परिभाषा नहीं वर्दी है। रैकेट में, दोनों फ़ोल्डरों के फ़ंक्शन में इनपुट का एक ही क्रम होता है, और इसलिए आप foldl को foldr से प्रतिस्थापित कर सकते हैं और एक ही परिणाम प्राप्त कर सकते हैं। यदि आप हास्केल संस्करण के साथ ऐसा करते हैं तो आपको एक अलग परिणाम मिल जाएगा (आमतौर पर) - और आप इसे दोनों के विभिन्न प्रकारों में देख सकते हैं।

  (वास्तव में, मुझे लगता है कि आदेश में एक उचित तुलना करने के लिए आप इन खिलौना सांख्यिक उदाहरण हैं, जहां प्रकार चर के दोनों पूर्णांक हैं बचना चाहिए।)

• यह अच्छा प्रतिफल जहां प्रोत्साहित किया जाता है है अपने अर्थपूर्ण मतभेदों के अनुसार foldl या foldr चुनने के लिए। मेरा अनुमान है कि हास्केल के आदेश के साथ आप ऑपरेशन के अनुसार चुनने की संभावना रखते हैं। इसके लिए आपके पास एक अच्छा उदाहरण है: आपने foldl का उपयोग किया है क्योंकि आप प्रत्येक नंबर को घटाना चाहते हैं - और यह ऐसी "स्पष्ट" पसंद है कि इस तथ्य को अनदेखा करना आसान है कि foldl आमतौर पर आलसी भाषा में एक खराब विकल्प है।

• एक और अंतर यह हास्केल संस्करण हमेशा की तरह रैकेट संस्करण की तुलना में अधिक सीमित है कि है: यह वास्तव में एक इनपुट सूची पर चल रही रैकेट सूचियों के किसी भी संख्या को स्वीकार कर सकते हैं, जबकि। इससे इनपुट फ़ंक्शन के लिए एक समान तर्क आदेश होना अधिक महत्वपूर्ण हो जाता है)।

• अंत में, यह, माना कि रैकेट "कई अन्य कार्यात्मक भाषाओं" से अलग गलत है के बाद से तह एक नई चाल से दूर है, और रैकेट जड़ों कि हास्केल (या इन अन्य भाषाओं) की तुलना में कहीं अधिक आयु के लोगों की है। प्रश्न अन्यथा पर जा सकता है: हास्केल का foldl एक अजीब तरीके से परिभाषित क्यों है? (और नहीं, (-) एक अच्छा बहाना नहीं है।)

ऐतिहासिक अद्यतन:

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

• पहले वहाँ लिस्प था, और का कोई जिक्र नहीं किसी भी तरह की आईएनजी "तह"। इसके बजाए, लिस्प में reduce है जो बहुत गैर-वर्दी है, खासकर यदि आप इसके प्रकार पर विचार करते हैं। उदाहरण के लिए, :from-end एक कीवर्ड तर्क है जो यह निर्धारित करता है कि यह बाएं या दायां स्कैन है और यह विभिन्न संचयक कार्यों का उपयोग करता है जिसका अर्थ है कि संचयक प्रकार उस कीवर्ड पर निर्भर करता है।यह अन्य हैक्स के अतिरिक्त है: आम तौर पर पहला मान सूची से लिया जाता है (जब तक कि आप :initial-value निर्दिष्ट नहीं करते)। अंत में, यदि आप एक :initial-value निर्दिष्ट नहीं करते हैं, और सूची खाली है, यह वास्तव में समारोह शून्य तर्क पर एक परिणाम प्राप्त करने के लिए लागू होगी।

  इसका मतलब यह है कि reduce आमतौर पर इसका नाम सुझाता है: मूल्यों की सूची को एक मान में कम करना, जहां दो प्रकार आमतौर पर समान होते हैं। यहां निष्कर्ष यह है कि यह फोल्डिंग के लिए एक समान उद्देश्य की सेवा कर रहा है, लेकिन यह लगभग उतना ही उपयोगी नहीं है जितना सामान्य सूची पुनरावृत्ति निर्माण करता है जिसे आप फोल्डिंग के साथ प्राप्त करते हैं। मुझे लगता है कि इसका मतलब है कि reduce और बाद के गुना संचालन के बीच कोई मजबूत संबंध नहीं है।

• पहले प्रासंगिक भाषा कि लिस्प अनुसरण करता है और एक उचित गुना है एमएल है। विकल्प है कि वहाँ बनाया गया था, के रूप में नीचे newacct के जवाब में बताया गया है, uniform types version साथ जाने के लिए था (यानी, क्या रैकेट का उपयोग करता है)।

• अगला संदर्भ पक्षी & वाडलर के आईटीएफपी (1 9 88) है, जो different types (जैसा हास्केल में) का उपयोग करता है। हालांकि, वे note in the appendix कि मिरांडा का एक ही प्रकार है (रैकेट में)।

• मिरांडा बाद में switched the argument order पर (यानी, रैकेट ऑर्डर से हास्केल में स्थानांतरित हो गया)। विशेष रूप से, कि पाठ का कहना है:

  चेतावनी - foldl की इस परिभाषा मिरांडा के पुराने संस्करणों में से अलग है। यहां एक जैसा है कि बर्ड एंड वाडलर (1 9 88) में। पुरानी परिभाषा में 'ओप' के दो तर्क थे।

• हास्केल ने विभिन्न प्रकारों सहित मिरांडा से बहुत सारी चीज़ें लीं। (लेकिन निश्चित रूप से मैं तारीखों पता नहीं है तो हो सकता है मिरांडा परिवर्तन हास्केल के कारण था।) किसी भी मामले में, यह इस बिंदु पर स्पष्ट है कोई आम सहमति नहीं थी, इसलिए उलट सवाल ऊपर रखती है।

• OCaml हास्केल दिशा के साथ चला गया और का उपयोग करता है different types

• मेरा अनुमान है कि यह है कि "कैसे कार्यक्रम डिजाइन करने के लिए" (उर्फ HtDP) मोटे तौर पर इसी अवधि में लिखा गया था, और वे same type चुना है। और वास्तव में, कि व्यायाम के बाद यह बस one of the built-in functions के रूप में उल्लेख किया गया है - हालांकि, कोई प्रेरणा या स्पष्टीकरण नहीं है। fold operations की

  रैकेट के कार्यान्वयन था, जाहिर है, "बनाया-इन" है कि यहाँ उल्लेख कर रहे हैं।

• फिर SRFI-1 आया, और विकल्प उसी प्रकार के संस्करण (रैकेट के रूप में) का उपयोग करना था। जॉन डेविड स्टोन, जो SRFI कि कहते हैं

  नोट में एक टिप्पणी में बताते हैं द्वारा यह निर्णय was question: एमआईटी योजना और हास्केल उनके reduce और fold कार्यों के लिए फ्लिप एफ के आर्ग आदेश।

  ओलिन बाद में addressed this: सब उन्होंने कहा था:

  अच्छा बिंदु है, लेकिन मैं दो कार्यों के बीच सामंजस्य चाहते हैं। राज्य के मूल्य पहले: srfi -1, एसएमएल राज्य के मूल्य पिछले: हास्केल

  विशेष रूप से ध्यान दें राज्य के मूल्य है, जो एक दृश्य जहां लगातार प्रकार की तुलना में एक संभवतः अधिक महत्वपूर्ण बात कर रहे हैं पता चलता है के अपने उपयोग ऑपरेटर आदेश।

Answer 4

एक जवाबी उदाहरण के रूप में मानक ML "किसी भी अन्य भाषा की तुलना में भिन्न" (एमएल एक बहुत पुरानी और प्रभावशाली कार्यात्मक भाषा है) के foldl भी इस तरह से काम करता है: http://www.standardml.org/Basis/list.html#SIG:LIST.foldl:VAL