継続を使ってOptionコンピュテーション式を実装する

前提

下記記事を読んでいることが前提となります。

コンピュテーション式の実装にStateを用いる - pocketberserkerの爆走

注意事項

  • 継続に関する解説はしません
  • この記事のコードが理解できなくてもコンピュテーション式は使うことができます

継続、しませんか

そもそもこの話は、コンピュテーション式のキーワードによって計算を継続するかどうか切り替えたい、というのが元々のお話でした。そして継続というと、この界隈にいれば一度は単語を聞いたことがあるだろう、継続モナドが真っ先に思いつくのが自然ですよね。

というわけで、件の OptionBuilder を、継続の概念を用いて実装してみましょう。

定義

先に実装を掲載しておきます。なお、 TryWith, TryFinally, While, For は既存と変更はないため、省略します。

type Cps<'T, 'R> = | Cps of (('T -> 'R) -> 'R)

type OptionBuilder internal () =
  member this.Zero() = Cps (fun k -> k None)
  member this.Return(x) = Cps (fun _ -> Some x)
  member this.ReturnFrom(x: _ option) = Cps (fun _ -> x)
  member this.Bind(x: _ option, f: _  -> Cps<_ option, _>) =
    match x with
    | Some x -> f x
    | None -> this.Zero()
  member this.Using(x: #IDisposable, f: #IDisposable -> Cps<_ option, _>) =
    try f x
    finally match box x with null -> () | notNull -> x.Dispose()
  member this.Combine(x, rest) =
    Cps (fun k -> match x with | Cps f -> f (fun value -> match rest () with | Cps g -> g k))
  member this.Delay(f) = f
  member this.Run(f) = match f () with | Cps x -> x id

Cps

わかりやすく(?)するために導入しています。

Zero

引数として受け取った関数に計算結果を適用するラムダ式を返します。

Return, ReturnFrom

引数の関数は使わずそのまま値を返します。こうすることで、後続の計算をすべて破棄しています。

Bind

渡された option が Some であれば Cps に束縛します。None の場合は Zero メソッドに依存します。今回は継続する形にしました。

Using

型が異なること以外は Bind と大した差はありません。

Combine

x, rest, 渡された引数の順に計算を行うラムダ式Cps でくるんで返します。

return などでは、引数として渡される関数は破棄しているので、後続の処理がひたすら破棄されるのがわかると思います。

Run

最終的に Option コンピュテーション式は Option を返したいので、 型を取り外して返します。

このコンピュテーション式は今まで通りの式をかけるのか?

少なくとも Basis.Core.OptionBuilder 用のテストは、テスト側は一切修正せずとも全件パスしたので、その範囲においては動作すると思われます。

継続渡しスタイルで

ここまでくると型いらないだろう、ということで。

type OptionBuilder internal () =
    member this.Zero() = fun k -> k None
    member this.Return(x) = fun _ -> Some x
    member this.ReturnFrom(x: _ option) = fun _ -> x
    member this.Bind(x, f) = x |> Option.map f |> getOrElse this.Zero
    member this.Using(x: #IDisposable, f) =
      try f x
      finally match box x with null -> () | notNull -> x.Dispose()
    member this.Combine(f, rest) = fun k -> f (fun _ -> rest () k)
    member this.Delay(f) = f
    member this.Run(f) = f () id

見た目はシンプルですが、シグネチャがすごいことになっています。が、定義する側としてはこちらのほうが楽ですね。

終わりに

というわけで、継続渡しスタイルはこういうところで使えるよ、という例でした。