StackOverflow निरंतरता इकाई

Question

में निम्नलिखित निरंतरता इकाई का उपयोग करना:

type ContinuationMonad() = 
    member this.Bind (m, f) = fun c -> m (fun a -> f a c) 
    member this.Return x = fun k -> k x 

let cont = ContinuationMonad() 

मैं देखना क्यों निम्नलिखित मुझे एक ढेर अतिप्रवाह देता है असफल: एक ओर जहां निम्नलिखित

let map f xs = 
    let rec map xs = 
     cont { 
      match xs with 
      | [] -> return [] 
      | x :: xs -> 
       let! xs = map xs 
       return f x :: xs 
     } 
    map xs id;; 

let q = [1..100000] |> map ((+) 1) 

नहीं करता है:

let map f xs = 
    let rec map xs = 
     cont { 
      match xs with 
      | [] -> return [] 
      | x :: xs -> 
       let! v = fun g -> g(f x) 
       let! xs = map xs 
       return v :: xs 
     } 
    map xs id;; 

let q = [1..100000] |> map ((+) 1) 

Answer 1

अपने उदाहरण को ठीक करने के लिए, इकाई की अपनी परिभाषा के लिए इस विधि जोड़ें:

member this.Delay(mk) = fun c -> mk() c 

जाहिर है बात यह है कि overflows map की पुनरावर्ती कॉल में बड़े इनपुट सूची के विनाश है। देरी से समस्या हल हो जाती है।

ध्यान रखें कि आपके दूसरे संस्करण map को पुनरावर्ती कॉल डालता है एक और let! जो Bind और एक अतिरिक्त लैम्ब्डा को desugars के पीछे, प्रभाव में map को पुनरावर्ती कॉल में देरी।

मुझे इस निष्कर्ष तक पहुंचने से पहले कुछ झूठे निशानों का पीछा करना पड़ा। StackOverflow को द्वारा भी फेंक दिया गया था (हालांकि उच्च N पर) जब तक रिकर्सिव कॉल में देरी हो रही है, तब तक StackOverflow को फेंक दिया गया है। जबकि F# TCO कुछ quirks है, OCaml अधिक सिद्ध है, इसलिए इस ने मुझे आश्वस्त किया है कि समस्या संकलक कोड और नहीं के साथ वास्तव में है:

let cReturn x = fun k -> k x 
let cBind m f = fun c -> m (fun a -> f a c) 

let map f xs = 
    (* inner map loop overflows trying to pattern-match long lists *) 
    let rec map xs = 
    match xs with 
     | [] -> cReturn [] 
     | x :: xs -> 
     cBind (map xs) (fun xs -> cReturn (f x :: xs)) in 
    map xs (fun x -> x) 

let map_fixed f xs = 
    (* works without overflowing by delaying the recursive call *) 
    let rec map xs = 
    match xs with 
     | [] -> cReturn [] 
     | x :: xs -> 
     cBind (fun c -> map xs c) (fun xs -> cReturn (f x :: xs)) in 
    map xs (fun x -> x) 

let map_fused f xs = 
    (* manually fused version avoids the problem by tail-calling `map` *) 
    let rec map xs k = 
    match xs with 
     | [] -> k [] 
     | x :: xs -> 
     map xs (fun xs -> k (f x :: xs)) in 
    map xs (fun x -> x) 

Answer 2

एफ # कंपाइलर कभी-कभी बहुत चालाक नहीं होता है - पहले मामले में यह map xs की गणना करता है तो f x और फिर उनसे जुड़ता है, इसलिए map xs पूंछ की स्थिति में नहीं है। दूसरे मामले में, यह आसानी से पूंछ की स्थिति में रहने के लिए map xs को पुन: व्यवस्थित कर सकता है।