Delay如何在continuation monad中正常工作以防止stackoverflow？

Question

这是一个参考问题:StackOverflow在延续monad中
与我玩了一点,需要一些澄清.

1)我想这个:

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

使得计算工作流程中的行为能够实现这些差异,如toyvo所示:

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

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

所以我并不完全明白什么是诀窍,什么时候
(fun c -> map xs c)只有不同的符号(map xs)

2)推理问题.- 在OP的第二个映射示例中,我发现它由于推理问题而无法编译v,因为它推断f为a -> b list而不是期望的a -> b.为什么以这种方式推断？如果let v = f x它会很好地推断.

3)在我看来,VS在工具提示中显示不准确的类型签名:monad的返回类型返回为:('e->'f)->f,而Bind的返回类型仅为'c->'b.- 它似乎('e->'f)只c在Bind情况下简化,或者我在这里遗漏了什么？

谢谢你的澄清,
托马斯

编辑 - 测试转储:

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:
map [1; 2] map [2] map [] cBind [] map [] cBind [3] map [2] map [] cBind [] map [] [2; 3]

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

编辑问题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

问题恰恰是与fun c -> map xs c 不一样map xs。它们在某种意义上具有相同的“含义”，但它们的运行时语义不同。在后一种情况下，计算表达式会导致立即调用作为参数map的函数xs（返回另一个函数作为结果）。另一方面，评估fun c -> map xs c 不会导致立即调用map! 调用会map被延迟，直到实际应用结果函数为止。这是防止堆栈溢出的关键区别。

关于你的其他问题，我不太明白你在第二个问题中问的是什么。对于您的第三个问题，编译器已推断出Bind. Bind您是对的，您可能期望的传统类型比这更具体，但是您可以在比严格必要的范围更广泛的上下文中调用这并不是真正的问题。如果您确实想要更具体的类型，您可以随时添加注释来约束签名。