暂停Monad - monadic类型应该是什么样的？

Question

我看到的典型Pause monad实现看起来像这样(基于来自Friendly F#by Giulia Costantini和Giuseppe Maggiore的第5章).

open System

type Process<'a> = unit -> 'a Step
and Step<'a> =
| Continue of 'a
| Paused of 'a Process

type PauseMonad () =
    member this.Return x = fun () -> Continue x
    member this.ReturnFrom x = x
    member this.Bind (result, rest) =
        fun () ->
            match result () with
            | Continue x -> rest x ()
            | Paused p -> Paused (this.Bind (p, rest))

let yield_ () =
    fun () ->
        Paused (fun () ->
            Continue ())

let get_process_step process_ step = do printfn "Process %d, step %d." process_ step
let get_last_process_step process_ = do printfn "Process %d finished." process_

let rec get_process process_ step_count =
    PauseMonad () {
        do! yield_ ()
        if step_count = 0 then
            do get_last_process_step process_
            return ()
        else
            do get_process_step process_ step_count
            return! get_process process_ <| step_count - 1
    }

let rec race p1 p2 =
    match p1 (), p2 () with
    | Continue _, _ -> do printfn "Process 1 finished first."
    | _, Continue _ -> do printfn "Process 2 finished first."
    | Paused p1_, Paused p2_ -> race (p1_) (p2_)

[<EntryPoint>]
let main _ =
    let process_1 = get_process 1 5
    let process_2 = get_process 2 7
    do race process_1 process_2
    0

这是Haskell中的类似实现.

但是,删除相互递归类型的Process和Step似乎更简单,只需使用单个递归类型Process,如下所示.

open System

type Process<'a> =
| Continue of 'a
| Paused of (unit -> 'a Process)

type PauseMonad () =
    member this.Return x = Continue x
    member this.ReturnFrom x = x
    member this.Bind (result, rest) =
        match result with
        | Continue x -> Paused (fun () -> rest x)
        | Paused p -> Paused (fun () -> this.Bind (p (), rest))

let yield_ () =
    Paused (fun () ->
        Continue ())

let get_process_step process_ step = do printfn "Process %d, step %d." process_ step
let get_last_process_step process_ = do printfn "Process %d finished." process_

let rec get_process process_ step_count =
    PauseMonad () {
        do! yield_ ()
        if step_count = 0 then
            do get_last_process_step process_
            return ()
        else
            do get_process_step process_ step_count
            return! get_process process_ <| step_count - 1
    }

let rec race p1 p2 =
    match p1, p2 with
    | Continue _, _ -> do printfn "Process 1 finished first."
    | _, Continue _ -> do printfn "Process 2 finished first."
    | Paused p1_, Paused p2_ -> race (p1_ ()) (p2_ ())

[<EntryPoint>]
let main _ =
    let process_1 = get_process 1 5
    let process_2 = get_process 2 7
    do race process_1 process_2
    0

这些实现中的任何一个都给出了相同的输出:

Process 1, step 5.
Process 2, step 7.
Process 1, step 4.
Process 2, step 6.
Process 1, step 3.
Process 2, step 5.
Process 1, step 2.
Process 2, step 4.
Process 1, step 1.
Process 2, step 3.
Process 1 finished.
Process 2, step 2.
Process 1 finished first.

我已经使两个实现尽可能相似以便于差异化.据我所知,唯一的区别是:

1. 在第一个版本中,yield_,PauseMonad.Return和PauseMonad.Bind会为返回值添加延迟.在第二个版本中,PauseMonad.Return在Paused包装器中添加了延迟.

2. 在第一个版本中,PauseMonad.Bind运行结果过程的一个步骤,以查看返回值是匹配Continue还是Paused.在第二个版本中,PauseMonad.Bind仅在确定它与Paused匹配后才运行结果过程的一个步骤.

3. 在第一个版本中,race运行每个进程的一个步骤,检查两个结果是否与Paused匹配,并使用其余进程进行递归.在第二个版本中,race检查两个进程是否匹配Paused,然后运行每个进程的一个步骤,并使用这些步骤的返回值进行递归.

第一个版本更好吗？

Answer 1

将代码从Haskell转换为F#有点棘手,因为Haskell是懒惰的,所以无论何时你看到任何值,比如'a在Haskell中,你都可以把它解释为unit -> 'a(或者更准确地说是Lazy<'a>) - 所以一切都是隐式延迟的.

但是,让我们只比较F#中的两个定义:

// Process is always delayed
type Process1<'a> = unit -> 'a Step1
and Step1<'a> = Continue1 of 'a | Paused1 of 'a Process1

// Process is a value or a delayed computation
type Process2<'a> = Continue2 of 'a | Paused2 of (unit -> 'a Process2)

关键区别在于,当您想要表示立即生成值的计算时,这必须是第一种情况下的完全求值,但它可以是执行某些操作的函数,并在第二种情况下返回值.例如:

let primitive1 : Process1<int> = fun () ->
  printfn "hi!"    // This will print when the computation is evaluated
  Continue1(42) )

let primitive2 : Process2<int> = 
  printfn "hi!"    // This will print immediately and returns a monadic value
  Continue2(42)

当您Delay向计算中添加成员时,这会变得很有趣,这使您可以在不评估副作用的情况下编写如下内容:

process { 
  printfn "Hi" // Using Process1, we can easily delay this
               // Using Process2, this is trickier (or we run it immediately)
  return 42 }

关于这一点有很多要说的,你可以在我写的关于计算表达式的最近文章中找到更多信息.