Stackoverflow en mónada continuación

Question

Usando la siguiente mónada continuación:

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

no veo por qué el siguiente me da un desbordamiento de pila:

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) 

Aunque la siguiente no:

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

para fijar su ejemplo, agregue este método para su definición de la mónada:

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

Al parecer, la parte que se desborda es la destrucción de la lista de entrada grande en la llamada recursiva de map. Retrasarlo resuelve el problema.

en cuenta que su segunda versión pone la llamada recursiva a map detrás de otro, que let! desugars a Bind y un lambda adicional, en efecto, el retraso de la llamada recursiva a map.

Tuve que buscar algunas pistas falsas antes de llegar a esta conclusión. Lo que ayudó fue observar que StackOverflow también es lanzado por OCaml (aunque a un valor más alto N) a menos que la llamada recursiva se demore. Mientras F# TCO tiene algunas peculiaridades, OCaml es más probada, por lo que este me ha convencido de que el problema es de hecho con el código y no el compilador:

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

El compilador F # a veces no es muy inteligente - en el primer caso calcula map xs luego f x y luego se une a ellos, por lo que map xs no está en posición de cola. En el segundo caso, puede reordenar el map xs para estar en posición de cola fácilmente.