如何在计算构建器中实现延迟？

Question

这是我到目前为止:

type Maybe<'a> = option<'a>

let succeed x = Some(x)

let fail = None

let bind rest p =
    match p with
        | None -> fail
        | Some r -> rest r

let rec whileLoop cond body =
    if cond() then
        match body() with
        | Some() ->
            whileLoop cond body
        | None ->
            fail
    else
        succeed()

let forLoop (xs : 'T seq) f =
    using (xs.GetEnumerator()) (fun it ->
            whileLoop
                (fun () -> it.MoveNext())
                (fun () -> it.Current |> f)
        )

whileLoop工作得很好,以支持for循环,但我不知道如何获得while循环支持.部分问题是while循环的转换使用delay,在这种情况下我无法弄清楚.下面明显的实现可能是错误的,因为它不会延迟计算,而是运行它!

let delay f = f()

没有延迟也会妨碍try...with和try...finally.

Answer 1

在F#中实际上有两种不同的实现连续构建器的方法.一种是使用monadic类型表示延迟计算(如果它支持某种表示延迟计算的方式,如kkm所示Async<'T>的unit -> option<'T>类型或类型).

但是,您也可以使用F#计算表达式的灵活性,并使用不同的类型作为返回值Delay.然后你需要相应地修改Combine操作并实现Run成员,但这一切都很好:

type OptionBuilder() = 
  member x.Bind(v, f) = Option.bind f v
  member x.Return(v) = Some v
  member x.Zero() = Some ()
  member x.Combine(v, f:unit -> _) = Option.bind f v
  member x.Delay(f : unit -> 'T) = f
  member x.Run(f) = f()
  member x.While(cond, f) =
    if cond() then x.Bind(f(), fun _ -> x.While(cond, f)) 
    else x.Zero()

let maybe = OptionBuilder()

诀窍是Delay当你有一个需要延迟的计算时F#编译器使用- 即:1)包装整个计算,2)当你顺序组合计算时,例如if在计算中使用和3)延迟while或for.

在上述定义,Delay成员返回unit -> M<'a>代替M<'a>,但这是完全正常的,因为Combine并While采取unit -> M<'a>作为他们的第二个参数.此外,通过添加Run评估函数,计算maybe { .. }块的结果(延迟函数),因为整个块传递给Run:

// As usual, the type of 'res' is 'Option<int>'
let res = maybe { 
    // The whole body is passed to `Delay` and then to `Run`
    let! a = Some 3
    let b = ref 0
    while !b < 10 do 
      let! n = Some () // This body will be delayed & passed to While
      incr b
    if a = 3 then printfn "got 3"
    else printfn "got something else"
    // Code following `if` is delayed and passed to Combine
    return a }

这是一种为非延迟类型定义计算构建器的方法,它最有可能比函数内的包装类型更有效(如在kkm的解决方案中),并且它不需要定义该类型的特殊延迟版本.

请注意,例如Haskell中不会发生此问题,因为这是一种惰性语言,因此不需要显式延迟计算.我认为F#转换非常优雅,因为它允许处理延迟的类型(使用Delay返回M<'a>)和仅表示立即结果的类型(使用Delay返回函数&Run).

Answer 2

根据monadic身份,你delay应该永远等同于

let delay f = bind (return ()) f

以来

val bind : M<'T> -> ('T -> M<'R>) -> M<'R>
val return : 'T -> M<'T>

该delay具有的签名

val delay : (unit -> M<'R>) -> M<'R>

'T被类型绑定到unit.请注意,您的bind函数的参数与惯例顺序相反bind p rest.这在技术上是相同的,但确实使阅读代码复杂化.

由于您将monadic类型定义为type Maybe<'a> = option<'a>,因此不会延迟计算,因为类型根本不包含任何计算,只包含一个值.所以你定义延迟在let delay f = f()理论上是正确的.但它对于while循环来说是不够的:循环的"body"将在其"测试条件"之前计算,实际上在bind绑定之前.要避免这种情况,可以使用额外的延迟层重新定义monad:不包装值,而是包装计算,该计算采用单位并计算值.

type Maybe<'a> = unit -> option<'a>

let return x = fun () -> Some(x)

let fail = fun() -> None

let bind p rest =
    match p() with
    | None -> fail
    | Some r -> rest r

请注意,包装计算直到bind函数内部才会运行,即直到参数bind绑定后才运行.

用上面的表达式,delay正确简化为

let delay f = fun () -> f()