StackOverflow in continuazione monade

Question

Utilizzando il seguente prosecuzione monade:

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

non riesco a capire perché il seguente mi dà un overflow dello stack:

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) 

Mentre il seguente non lo fa:

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

per risolvere il tuo esempio, aggiungere questo metodo per la sua definizione della monade:

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

A quanto pare la parte che trabocca è la distruzione della lista di input di grandi dimensioni nella chiamata ricorsiva di map. Ritardare risolve il problema.

Nota che la seconda versione mette la chiamata ricorsiva a map dietro un'altra let! che desugars ad Bind ed un lambda in più, in effetti ritardare la chiamata ricorsiva a map.

Ho dovuto seguire alcune false piste prima di giungere a questa conclusione. Ciò che ha aiutato è stato osservare che StackOverflow viene generato anche da OCaml (anche se con un valore superiore a N) a meno che la chiamata ricorsiva non venga ritardata. Mentre F# TCO ha alcune stranezze, OCaml è più provata, quindi questo mi ha convinto che il problema è in effetti con il codice e non il compilatore:

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

Il compilatore F # a volte non è molto intelligente - nel primo caso calcola map xs quindi f x e quindi si uniscono a loro, quindi map xs non si trova in una posizione di coda. Nel secondo caso, è possibile riordinare lo map xs in posizione di coda facilmente.