List.fold और List.foldBack

Question

के बीच अंतर का उदाहरण List.fold और List.foldBack के बीच अंतर की मेरी समझ यह है कि फ़ोल्डबैक एक रिवर्स ऑर्डर में अपनी सूची में पुनरावृत्त करता है। दोनों कार्य सूची में वस्तुओं से परिणाम जमा करते हैं।

मुझे एक अच्छे उदाहरण के साथ आने में परेशानी हो रही है जहां एक सूची में फोल्ड करना बेहतर है। उदाहरणों में जिनके साथ मैं आया हूं, परिणाम फोल्ड लॉजिक दोनों के लिए समान हैं, अगर फ़ंक्शन तर्क एक ही चीज़ करता है।

[<Fact>] 
let ``List.foldBack accumulating a value from the right to the left``() = 
    let list = [1..5]  
    let fFoldBack x acc = 
     acc - x 

    let fFold acc x = 
     acc - x 

    let foldBackResult = List.foldBack fFoldBack list 0 
    let foldResult = List.fold fFold 0 list 

    Assert.Equal(-15, foldBackResult) // 0 - 5 - 4 - 3 - 2 - 1 
    Assert.Equal(-15, foldResult) //  0 - 1 - 2 - 3 - 4 - 5 

Answer 1

आप अपने उदाहरण में एक फर्क नहीं दिख रहा है, क्योंकि आप एक समारोह चुना है इस तरह है कि किसी भी x1 और x2 के लिए:

(acc - x1) - x2 = (acc - x2) - x1 

तो यह में कोई फर्क नहीं पड़ता कि क्या आपको के माध्यम से जाना सूची, आपको एक ही परिणाम मिल जाएगा।

x1 :: (x2 :: acc) <> x2 :: (x1 :: acc) 

तो निम्नलिखित निकलेगा अलग परिणाम: एक खाली परिणाम सूची के साथ

List.fold (fun acc x -> x :: acc) [] [1; 2; 3; 4; 5] 
// val it : int list = [5; 4; 3; 2; 1] 

List.foldBack (fun x acc -> x :: acc) [1; 2; 3; 4; 5] [];; 
// val it : int list = [1; 2; 3; 4; 5] 

List.fold शुरू होता है और चला जाता है

सूची निर्माण समारोह का एक उदाहरण है जिसके लिए यह मामला नहीं है है इनपुट के माध्यम से आगे बढ़ें, परिणाम सूची के सामने प्रत्येक तत्व जोड़ना; इसलिए अंतिम परिणाम रिवर्स ऑर्डर में है।

List.foldBack, दूसरी तरफ, इनपुट के माध्यम से पिछड़ा हो जाता है; इसलिए परिणाम सूची के सामने नए जोड़े गए प्रत्येक तत्व मूल सूची में सामने थे। तो अंतिम परिणाम मूल के समान सूची है।

Answer 2

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

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

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

प्रोग्राम पूर्णांक की सूची से प्रोग्राम बनाने के तीन अलग-अलग तरीकों का उपयोग करता है। पहला, make_list_printer, जिसे हम प्राप्त करने की कोशिश कर रहे हैं, इसका प्रदर्शन करने के लिए, किसी भी गुना के साथ पुनरावर्ती रूप से परिभाषित किया गया है। दूसरा, make_list_printer_foldBack, उसी परिणाम को प्राप्त करने के लिए foldBack का उपयोग करता है। तीसरा, make_list_printer_fold, यह दर्शाता है कि यह गलत परिणाम कैसे उत्पन्न करता है, यह देखने के लिए fold का उपयोग करता है।

मैंने ज्यादातर ओकैम में कोड किया है, एफ # नहीं, इसलिए मैं क्षमा चाहता हूं कि नीचे दिए गए कुछ कोडिंग सम्मेलनों को वास्तव में एफ # में उचित शैली नहीं माना जाता है। मैंने एफ # दुभाषिया में इसका परीक्षण किया, हालांकि, और यह काम करता है।

(* Data structure of our mini-language. *) 
type prog = 
| End 
| Print of int * prog 

(* Builds a program recursively. *) 
let rec make_list_printer = function 
| [] -> End 
| i :: program -> Print (i, make_list_printer program) 

(* Builds a program using foldBack. *) 
let make_list_printer_foldBack ints = 
    List.foldBack (fun i p -> Print (i, p)) ints End 

(* Builds a program in the wrong direction. *) 
let make_list_printer_fold ints = 
    List.fold (fun p i -> Print (i, p)) End ints 

(* The interpreter for our mini-language. *) 
let rec run_list_printer = function 
| End -> 
    printfn "" 
| Print (i, program) -> 
    printf "%d " i; 
    run_list_printer program 

(* Build and run three different programs based on the same list of numbers. *) 
let() = 
    let base_list = [1; 2; 3; 4; 5] in 
    let a = make_list_printer   base_list in 
    let b = make_list_printer_foldBack base_list in 
    let c = make_list_printer_fold  base_list in 
    run_list_printer a; 
    run_list_printer b; 
    run_list_printer c 

उत्पादन है कि मैं जब मैं चलाने यह है:

1 2 3 4 5 
1 2 3 4 5 
5 4 3 2 1