Пауза Монад - Каким должен выглядеть монадический тип?

Question

Типичная реализация монады Пауза, которую я вижу, выглядит так (на основе главы 5 из Friendly F # Джулии Костантини и Джузеппе Маджоре).

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. 

Я сделал две реализации похожи, как можно облегчить разностей. Насколько я могу судить, только различия таковы:

1. В первой версии, yield_, PauseMonad.Return и PauseMonad.Bind добавить задержки для возвращаемых значений. Во второй версии PauseMonad.Return добавляет задержку внутри оболочки Paused.

2. В первой версии PauseMonad.Bind выполняет один шаг процесса результата, чтобы узнать, соответствует ли возвращаемое значение Continue или Paused. Во второй версии PauseMonad.Bind запускает один шаг процесса результата только после определения, что он соответствует Paused.

3. В первой версии гонка проходит один шаг каждого процесса, проверяет, что оба результата совпадают с Приостановленными, и повторяется с остальными процессами. Во второй версии, гонка проверяет, что оба процесса соответствуют 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 } 

Существует много скажем об этом, и вы можете найти дополнительную информацию in a recent article I wrote about computation expressions.