StackOverflow trong việc tiếp tục đơn nguyên

Question

Sử dụng đơn nguyên tiếp tục sau:

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() 

Tôi không thấy lý do tại sao những điều sau đây mang lại cho tôi một chồng tràn:

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) 

Trong khi sau không:

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

Để khắc phục ví dụ của bạn, thêm phương pháp này để định nghĩa lại các đơn nguyên:

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

Rõ ràng phần mà tràn là sự hủy diệt của danh sách đầu vào lớn trong cuộc gọi đệ quy của map. Trì hoãn nó giải quyết vấn đề.

Lưu ý rằng phiên bản thứ hai của bạn đặt cuộc gọi đệ quy để map đằng sau một let! mà desugars để Bind và một lambda thêm, có hiệu lực kéo dài thời gian cuộc gọi đệ quy để map.

Tôi đã phải theo đuổi một vài đường mòn sai trước khi đạt được kết luận này. Những gì đã giúp được quan sát rằng StackOverflow được ném bởi OCaml là tốt (mặc dù ở một cao hơn N) trừ khi cuộc gọi đệ quy bị trì hoãn. Trong khi F# TCO có một số tật, OCaml là đã được chứng minh nhiều hơn, vì vậy đây đã thuyết phục tôi rằng vấn đề thực sự là với mã và không trình biên dịch:

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

Trình biên dịch F # đôi khi không thông minh lắm - trong trường hợp đầu tiên nó tính map xs rồi f x và sau đó gia nhập chúng, vì vậy map xs không ở vị trí đuôi. Trong trường hợp thứ hai, nó có thể sắp xếp lại các map xs để ở vị trí đuôi dễ dàng.