Come funziona esattamente il delay nella monad di continuazione per impedire lo stackoverflow?

Question

Questa è una domanda di riferimento a questo: StackOverflow in continuation monad
con cui ho giocato un po 'e avrei bisogno di alcuni chiarimenti.

1) Suppongo che questo:

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

rende il comportamento del flusso di lavoro computazionale fare il diffrence come mostrato dalla toyvo tra questi:

cBind (map xs) (fun xs -> cReturn (f x :: xs)) 

cBind (fun c -> map xs c) (fun xs -> cReturn (f x :: xs)) 

quindi non esattamente capire quale sia la trucco, quando
(fun c -> map xs c) è solo notazione differente di (map xs)

2) Inferere problema. - Nell'esempio della seconda mappa di OP ho scoperto che non viene compilato a causa del problema di inferenza con il valore v, perché inferisce f come a -> b list, anziché il desiderato a -> b. Perché lo sottende in questo modo? Nel caso let v = f x si dedurrebbe bene.

3) Mi sembra che VS mostra di tipo firme imprecisi inseriti nelle descrizioni comandi: tipo di ritorno del ritorno del monade è: ('e->'f)->f, mentre il tipo di ritorno del Bind è soltanto 'c->'b. -Sembra semplificare lo nel caso Bind, o mi manca qualcosa qui?

Grazie per il chiarimento,
Tomas

Edit - test discarica:

let cReturn x = fun k -> k x 
let cBind m f = 
    printfn "cBind %A" <| m id 
    fun c -> m (fun a -> f a c) 

let map_fixed f xs = 
    let rec map xs = 
    printfn "map %A" xs 
    match xs with 
     | [] -> cReturn [] 
     | x :: xs -> cBind (fun c -> map xs c) (fun xs -> cReturn (f x :: xs)) 
    map xs (fun x -> x) 

let map f xs = 
    let rec map xs = 
    printfn "map %A" xs 
    match xs with 
     | [] -> cReturn [] 
     | x :: xs -> cBind (map xs) (fun xs -> cReturn (f x :: xs)) 
    map xs (fun x -> x) 

[1..2] |> map_fixed ((+) 1) |> printfn "%A" 
[1..2] |> map ((+) 1) |> printfn "%A" 

MAP_FIXED:
mappa [1; 2] mappa [2] mappa [] cBind [] map [] cBind [3] mappa [2] mappa [] cBind [] map [] [2; 3]

mappa:
mappa [1; 2] mappa [2] mappa [] cBind [] cBind [3] [2; 3]

Modifica alla domanda 2:

let map f xs = 
    let rec map xs = 
     cont { 
      match xs with 
      | [] -> return [] 
      | x :: xs -> 
       let v = f x // Inference ok 
       //let! v = cont { return f x } // ! Inference issue - question 2 
       let! xs = map xs 
       return v :: xs 
     } 
    map xs id 

Answer 1

Il problema è esattamente questo fun c -> map xs cnon è lo stesso dimap xs. Hanno lo stesso "significato" in un certo senso, ma la loro semantica runtime è diversa. In quest'ultimo caso, la valutazione dell'espressione comporta una chiamata immediata alla funzione map con xs come argomento (restituendo un'altra funzione come risultato). D'altra parte, la valutazione di fun c -> map xs cnon corrisponde a in una chiamata immediata a map! La chiamata a map viene ritardata finché non viene effettivamente applicata la funzione risultante. Questa è la differenza fondamentale che impedisce un overflow dello stack.

Per quanto riguarda le altre domande, non riesco a capire cosa stai chiedendo nella tua seconda domanda. Per la terza domanda, il compilatore ha inferito il tipo più generale possibile per Bind. Hai ragione che il tipo tradizionale che potresti aspettarti è più specifico di questo, ma non è proprio un problema che puoi chiamare Bind in un insieme più ampio di contesti di quanto sia strettamente necessario. E se vuoi davvero un tipo più specifico, puoi sempre aggiungere annotazioni per limitare la firma.