मैं पूंछ-पुनरावर्ती सूची को कैसे कार्यान्वित कर सकता हूं?

Question

इस तरह एक साधारण संलग्न समारोह (एफ # में):

let rec app s t = 
    match s with 
     | [] -> t 
     | (x::ss) -> x :: (app ss t) 

, दुर्घटना होगा जब रों बड़ा हो जाता है समारोह पूंछ पुनरावर्ती नहीं है, क्योंकि। मैंने देखा कि एफ # का मानक एपेंड फ़ंक्शन बड़ी सूचियों से क्रैश नहीं होता है, इसलिए इसे अलग-अलग कार्यान्वित किया जाना चाहिए। तो मैंने सोचा: एक पूंछ की पुनरावृत्ति परिभाषा की तरह दिखने की परिभाषा कैसी दिखती है? मैं इस तरह कुछ आया:

let rec comb s t = 
    match s with 
     | [] -> t 
     | (x::ss) -> comb ss (x::t) 
let app2 s t = comb (List.rev s) t 

जो काम करता है, लेकिन अजीब दिखता है। क्या एक और सुरुचिपूर्ण परिभाषा है?

Answer 1

पारंपरिक (नहीं पूंछ पुनरावर्ती)

let rec append a b = 
    match a, b with 
    | [], ys -> ys 
    | x::xs, ys -> x::append xs ys 

एक संचायक के साथ (पूंछ पुनरावर्ती)

let append2 a b = 
    let rec loop acc = function 
     | [] -> acc 
     | x::xs -> loop (x::acc) xs 
    loop b (List.rev a) 

निरंतरता के साथ (पूंछ पुनरावर्ती)

let append3 a b = 
    let rec append = function 
     | cont, [], ys -> cont ys 
     | cont, x::xs, ys -> append ((fun acc -> cont (x::acc)), xs, ys) 
    append(id, a, b) 

किसी भी गैर-पूंछ रिकर्सिव फ़ंक्शन को निरंतरता के साथ पुनरावृत्ति के रूप में परिवर्तित करने के लिए यह बहुत सीधी-आगे है, लेकिन मैं व्यक्तिगत रूप से सीधे-आगे पठनीयता के लिए संचयक पसंद करता हूं।

Answer 2

एफ # स्रोतों पर एक त्वरित नज़र से, ऐसा लगता है कि पूंछ आंतरिक रूप से परिवर्तनीय है। एक आसान समाधान दूसरी सूची में अपने तत्वों को पेश करने से पहले पहली सूची को पीछे हटाना होगा। सूची के साथ-साथ, पूंछ को पुन: लागू करने के लिए तुच्छ हैं।

Answer 3

क्या जूलियट तैनात करने के अलावा:

अनुक्रम का उपयोग करते हुए भाव
आंतरिक रूप से, अनुक्रम भाव पूंछ पुनरावर्ती कोड उत्पन्न है, तो यह ठीक काम करता है।

let append xs ys = 
    [ yield! xs 
    yield! ys ] 

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

let append (xs:'a[]) (ys:'a[]) = 
    let ra = new ResizeArray<_>(xs) 
    for y in ys do ra.Add(y) 
    ra |> List.ofSeq 

यह कुछ स्थितियों में उपयोगी हो सकता है, लेकिन मैं आम तौर पर एफ # कोड में उत्परिवर्तन से बचने चाहते हैं।