फ़ोल्डल। फ़ोल्डर फ़ंक्शन संरचना - हास्केल

Question

तो, मैं वास्तव में folding.foldr संरचना को समझने की कोशिश कर रहा हूं।

(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]] 

परिणाम 22 है, लेकिन क्या वास्तव में यहाँ क्या हो रहा है: यहाँ एक उदाहरण है?

मेरे लिए ऐसा लगता है कि यह हो रहा है: foldl (+) 1 [6,15]। मेरा संदेह foldr भाग से संबंधित है। क्या यह सभी उप-सूचियों में 1 जोड़ना नहीं चाहिए? इस तरह: foldr (+) 1 [1,2,3]। मेरे सिर में 1 केवल एक बार जोड़ा जाता है, क्या यह सही है? (शायद नहीं, लेकिन मैं जानना चाहता हूं कि क्यों/क्यों!)।

मैं बहुत उलझन में हूं (और शायद सभी भ्रम, हाहा)। धन्यवाद!

Answer 1

(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]] 

foldl (foldr (+)) 1 [[1,2,3],[4,5,6]] 

तो तुम

foldl (foldr (+)) (foldr (+) 1 [1,2,3]) [[4,5,6]] 

foldl का पहला कदम के बाद

, या

foldl (foldr (+)) 7 [[4,5,6]] 

प्राप्त करता है, तो हमारे द्वारा लागू foldr (का मूल्यांकन जब तक stric हो जाता है tness विश्लेषक में लात मारता है, यह वास्तव में एक unevaluated thunk रहेगा जब तक foldl पूरी सूची चल गया है होगा, लेकिन अगले अभिव्यक्ति यह मूल्यांकन किया है) के साथ और अधिक पठनीय है, और कहा कि

foldl (foldr (+)) (foldr (+) 7 [4,5,6]) [] 

और अंत में

foldl (foldr (+)) 22 [] 
~> 22 

हो जाता है

Answer 2

चलो foldl . foldr की जांच करें। उनके प्रकार

foldl :: (a -> b -> a) -> (a -> [b] -> a) 
foldr :: (c -> d -> d) -> (d -> [c] -> d) 

मैं जानबूझकर अलग प्रकार चर का इस्तेमाल किया और मैं कोष्ठकों जोड़ा ताकि यह अधिक स्पष्ट हो जाता है कि हम उन्हें अब देखना एक तर्क के कार्यों के रूप में (और उनके परिणामों के कार्य हैं) कर रहे हैं। foldl पर देखते हुए हम देखते हैं कि यह एक प्रकार का भारोत्तोलन कार्य है: aa से b का उपयोग करके एक समारोह को देखते हुए, हम इसे उठाते हैं ताकि यह [b] (गणना को दोहराकर) पर काम करे। फ़ंक्शन foldr समान है, केवल तर्कों के उलट के साथ।

अब क्या होता है यदि हम foldl . foldr लागू करते हैं? सबसे पहले, आइए टाइप प्राप्त करें: हमें प्रकार चर को एकीकृत करना है ताकि foldr का परिणाम foldl के तर्क से मेल खाता हो। a = d, b = [c]: तो हम विकल्प है

foldl :: (d -> [c] -> d) -> (d -> [[c]] -> d) 
foldr :: (c -> d -> d) -> (d -> [c] -> d) 

तो हम

foldl . foldr :: (c -> d -> d) -> (d -> [[c]] -> d) 

पाने और इसका अर्थ क्या है? सबसे पहले, foldr सूचियों पर काम करने के लिए c -> d -> d के तर्क को लिफ्ट करता है, और इसके तर्कों को उलट देता है ताकि हमें d -> [c] -> d मिल सके। अगला, foldl[[c]] पर काम करने के लिए इस फ़ंक्शन को फिर से ले जाता है - [c] की सूचियां।

आपके मामले में, (+) उठाया गया ऑपरेशन सहयोगी है, इसलिए हमें इसके आवेदन के आदेश की परवाह नहीं है। डबल उठाने से बस एक ऐसा फ़ंक्शन बन जाता है जो सभी नेस्टेड तत्वों पर ऑपरेशन लागू करता है।

अगर हम सिर्फ foldl उपयोग करते हैं, प्रभाव और भी अच्छे है: हम

foldl . foldl . foldl . foldl 
    :: (a -> b -> a) -> (a -> [[[[b]]]] -> a) 

Answer 3

वास्तव में, (foldl.foldr) f z xs === foldr f z (concat $ reverse xs) में की तरह, कई बार उठा सकते हैं।

भले ही f एक सहयोगी संचालन है, अनुप्रयोगों का सही अनुक्रम, क्योंकि इसका प्रदर्शन पर असर पड़ सकता है।

हम शुरू

(foldl.foldr) f z xs 
foldl (foldr f) z xs 

g = foldr f और [x1,x2,...,xn_1,xn] = xs एक पल के लिए के साथ लेखन के साथ, इस

(foldl.foldr) 1 [[1,2,3],[4,5,6]] 
4+(5+(6+( 1+(2+(3+ 1))))) 
22 

बुद्धि के लिए है आपके मामले में

(...((z `g` x1) `g` x2) ... `g` xn) 
(`g` xn) ((`g` xn_1) ... ((`g` x1) z) ...) 
foldr f z $ concat [xn,xn_1, ..., x1] 
foldr f z $ concat $ reverse xs 

तो है सही कमी अनुक्रम ,

Prelude> (foldl.foldr) (:) [] [[1..3],[4..6],[7..8]] 
[7,8,4,5,6,1,2,3] 

---

इसी

, (foldl.foldl) f z xs == foldl f z $ concat xs। snoc a b = a++[b],

Prelude> (foldl.foldl) snoc [] [[1..3],[4..6],[7..8]] 
[1,2,3,4,5,6,7,8] 

इसके अलावा, (foldl.foldl.foldl) f z xs == (foldl.foldl) (foldl f) z xs == foldl (foldl f) z $ concat xs == (foldl.foldl) f z $ concat xs == foldl f z $ concat (concat xs), आदि .:

Prelude> (foldl.foldl.foldl) snoc [] [[[1..3],[4..6]],[[7..8]]] 
[1,2,3,4,5,6,7,8] 
Prelude> (foldl.foldr.foldl) snoc [] [[[1..3],[4..6]],[[7..8]]] 
[7,8,1,2,3,4,5,6] 
Prelude> (foldl.foldl.foldr) (:) [] [[[1..3],[4..6]],[[7..8]]] 
[7,8,4,5,6,1,2,3]