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

Question

我看到的典型 Pause monad 实现如下所示（基于 Giulia Costantini 和 Giuseppe Maggiore 编写的 Friendly F# 的第 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

Here 是 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.

我已经使这两个实现尽可能相似以便于区分。据我所知，唯一的区别是：

在第一个版本中，yield_、PauseMonad.Return 和 PauseMonad.Bind 向 return 值添加延迟。在第二个版本中，PauseMonad.Return 在 Paused 包装器中添加了延迟。
在第一个版本中，PauseMonad.Bind 运行结果过程的一个步骤，以查看 return 值是否匹配 Continue 或 Paused。在第二个版本中，PauseMonad.Bind只有在确定匹配Paused后才运行结果过程的一个步骤。
在第一个版本中，race 运行每个进程的一个步骤，检查两个结果是否与 Paused 匹配，然后对剩余进程进行递归。在第二个版本中，race 检查两个进程是否匹配 Paused，然后运行每个进程的一个步骤，并使用这些步骤的 return 值进行递归。

有没有第一个版本更好的原因？

Answer 1

将代码从 Haskell 转换为 F# 有点棘手，因为 Haskell 是惰性的，所以每当您看到任何值时，在 Haskell 中说 'a，您可以将其解释为 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)

关键区别在于，当您想要表示立即产生值的计算时，在第一种情况下，这必须是一个完全评估的值，但它可以是一个执行某些操作的函数 returns 第二种情况下的值。例如：

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 }

对此有很多话要说，您可以找到更多信息in a recent article I wrote about computation expressions。

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

Pause Monad - What should the monadic type look like?

monads

f#