延迟是如何在continuation monad中准确工作以防止stackoverflow的

Question

这是一个参考问题：continuation monad中的StackOverflow
我和他打了一点比赛，需要澄清一下。

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-在Bind的情况下，它似乎将('e->'f)简化为只有c，或者我在这里遗漏了什么？

感谢您的澄清，
tomas

编辑-测试转储：

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"

映射固定（_F）：
地图[1；2]地图[2]地图[]cBind[]地图[]cBind[3]地图[2]地图[]cBind[]地图[][2；3]

地图：
地图[1；2]地图[2]地图[]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不同。在某种意义上，它们具有相同的"含义"，但它们的运行时语义不同。在后一种情况下，对表达式求值会导致立即调用以xs为自变量的map函数（返回另一个函数作为结果）。另一方面，评估fun c -> map xs c不会导致立即调用map！对map的调用被延迟，直到实际应用得到的函数为止。这是防止堆栈溢出的关键区别。

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