2011-03-06 12 views
5

हास्केल में दो कार्य हैं जो किसी एक मूल्य को कम करने के लिए वस्तुओं की सूची पर एक ऑपरेशन करने की अनुमति देते हैं। (निश्चित रूप से दो से अधिक हैं, लेकिन ये दो हैं जिनमें मुझे रूचि है।) वे foldl1 और foldr1 हैं। यदि ऑपरेशन किया जाना है commutative (जैसे अतिरिक्त), इससे कोई फर्क नहीं पड़ता कि आप इनमें से किस का उपयोग करते हैं। नतीजा वही होगा। हालांकि, यदि ऑपरेशन कम्यूटेटिव (उदा।, घटाव) है, तो दोनों उत्पाद बहुत अलग परिणाम उत्पन्न करते हैं। उदाहरण के लिए:जे में हास्केल के फ़ोल्ड 1 को कार्यान्वित करने का सबसे प्रभावी तरीका क्या है?

foldr1 (-) [1..9] 
foldl1 (-) [1..9] 

पहले का जवाब 5 और दूसरा, -43 है। foldr1 की जम्मू बराबर डालने क्रिया विशेषण, /, उदाहरण के लिए,

-/ 1+i.9 

जो foldr1 (-) [1..9] के बराबर है। मैं जे में एक क्रियाविधि बनाना चाहता हूं जो सम्मिलित विज्ञापन की तरह काम करता है, लेकिन दाईं ओर बाएं गुना है। सबसे अच्छा मैं के साथ आ सकता है निम्नलिखित है:

foldl =: 1 : 'u~/@|.' 

इस प्रकार, एक कह सकते हैं:

- foldl 1+i.9 

और मिल -43 जवाब है, जो है क्या एक छोड़ दिया गुना से आशा की जाती है के रूप में।

क्या जे में ऐसा करने का कोई बेहतर तरीका है? किसी कारण से, y तर्क को उलटना मेरे लिए प्रभावी प्रतीत नहीं होता है। शायद इसका सहारा लेने के बिना ऐसा करने का कोई तरीका है।

+1

मुझे नहीं पता कि सरणी फिसलने के अलावा चीज जैसी कोई चीज है, भले ही यह कितना व्यावहारिक लगे। कोई सोचता है (या आशा करता है) हास्केल ऐसा नहीं करता है और केवल अंत से कार्य करता है ... – MPelletier

+0

मेरा मतलब था "कोई फर्क नहीं पड़ता कि कैसे अप्रचलित है।" – MPelletier

उत्तर

2

मुझे नहीं लगता कि वहाँ एक बेहतर तरीका की तुलना में है कि आप का वर्णन छोड़ दिया गुना करने के लिए है:

(v~)/(|. list) 

यह एक बहुत ही प्राकृतिक तरीके से, एक लगभग "शाब्दिक" परिभाषा के कार्यान्वयन है। सूची को वापस करने की लागत बहुत छोटी है (आईएमओ)।

foldl_once =: 1 :'(u/0 1 { y), (2}. y)' 
foldl =: 1 :'(u foldl_once)^:(<:#y) y' 
तो

:

बाईं गुना को लागू करने की अन्य स्पष्ट रास्ता

new_list = (first v second) v rest 

जैसे स्थापित करने के लिए है

- foldl >:i.9 
_43 

लेकिन अपने तरीके से करता है बहुत की तुलना में बेहतर यह अंतरिक्ष और समय दोनों में।

+0

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

1
($:@}:-{:)^:(1<#) 1+i.9 
_43 

कोई विचार नहीं है कि यह और अधिक (या कम) कुशल है।

+0

कहना मुश्किल है। 4500 से नीचे की संख्या के साथ, आपका समाधान और मेरा तात्कालिक है। उसके बाद, आपका स्टैक त्रुटि का कारण बनता है और मेरा काम ठीक है। तो उस अर्थ में, मेरा अधिक कुशल है, लेकिन संसाधनों को अलग करना कहना मुश्किल है जो तेज़ है। –

+0

ओह, और मैंने सोचा कि मैं जोड़ूंगा कि आपका चालाक और शैक्षिक दोनों ही है। –

संबंधित मुद्दे