Combine Deep Dives - ぐるぐる～

この記事はF# Advent Calendar 2015の17日目の記事です。

今日はコンピュテーション式の Combine について取り上げます。

詳説コンピュテーション式をある程度理解していると分かりやすいかもしれません。

内容を簡単にまとめると、

Delay の中で受け取った関数を実行する場合、副作用を考慮したときに問題が起こらないか考えること
ゼロ値がある型で Combine を実装するときは、Delay の中で受け取った関数を実行せずに、Combine の中で実行すること
ゼロ値がない型で Combine を実装するときは、Combine の実装は Bind に流し、Zero は M<unit> を返すように実装すること

です。

Combineの目的

Combine は、コンピュテーション式の2つの式を繋ぐために使います。コンピュテーション式中の変換対象となる式を ce プレフィックスで表す場合、ce1; ce2 という式*1は Combine を使って下記のように変換されます。

(* bはビルダークラスのインスタンス *)
b.Combine(ce1の変換結果, b.Delay(fun () -> ce2の変換結果))

あれあれ、Delay というメソッドが出てきました。このように、Combine を使うためには Delay を実装する必要があります。

Delayの実装

Delay をどうするかは、2通りの方法があります。まずは、単純な方法から見てみます。

Delayの実装方法その1

Combine の引数としては、ce1 の変換結果と ce2 の変換結果がそのまま渡されるのがとりあえずわかりやすい気がしませんか？そういうことにしておくと、Delay の実装はこう決まります。

(* 引数の関数を実行するだけ *)
member __.Delay(f) = f ()

こうすることで、Combine には ce1 の変換結果と ce2 の変換結果がそのまま渡されます。この実装方針を取った場合、Combine のシグネチャはMSDNのコンピュテーション式のページにあるように、

M<'T> * M<'T> -> M<'T>

または

M<unit> * M<'T> -> M<'T>

となるでしょう。実際に具体例でみてみます。

listの場合

'a list の Combine を考えてみます。

list {
  yield 10
  yield 20
}

とあったとき、望む結果が [10; 20] だとすると、Combine が意味するのはリスト同士の結合、つまり List.append です。実装してみましょう。

type ListBuilder () =
  member __.Yield(x) = [x]
  member __.Delay(f) = f ()
  member __.Combine(xs, ys) = List.append xs ys

この場合、Combine のシグネチャは 'a list * 'a list -> 'a list になります。

optionの場合

'a option の Combine を考えてみます。

option {
  if cond then
    return 10
  return 20
}

とあり、cond によって

`cond` の値	結果
`true`	`Some 10`
`false`	`Some 20`

となってほしいとします。この場合、Combine が意味するのは match による分岐です。 else の伴わない if には Zero も必要なので、実装します。

type OptionBuilder () =
  member __.Return(x) = Some x
  member __.Zero() = None
  member __.Delay(f) = f ()
  member __.Combine(x, y) =
    match x with
    | Some x -> Some x
    | None -> y

この場合、Combine のシグネチャは 'a option * 'a option -> 'a option になります。

Delayの実装方法その2

上の Delay の実装、無名関数でくるんだものをそのまま実行しており、Delay の存在意義が分かりません。無名関数でくるんだ結果を Delay に渡すことなどせずに、直接 Combine に渡してくれ、と思ってしまっても仕方ありません。

では、なぜ Delay なんてものが Combine の変換に出てくるのでしょうか？上で実装した OptionBuilder を使って、上の Delay の実装には問題があることを見てみます。

let option = OptionBuilder()

option {
  if true then return 10
  printfn "hello"
  return 20
}

このコードは Some 10 を返しますが、「hello」も表示されてしまいます。コンピュテーション式の部分を変換してみると、次のようになります*2。

let b = option
b.Combine(
  (if true then b.Return(10) else b.Zero()),
  b.Delay(fun () -> printfn "hello"; b.Return(20)))

Delay は受け取ったラムダ式をそのまま実行するように実装しましたので、Combine を呼び出す前にラムダ式の中の式が実行されてしまうのです。これを避けるためには、Delay に渡ってきた関数は実際に必要になるまで実行を遅延する必要があります。

この方針で実装した OptionBuilder は下記のとおりです。

type OptionBuilder () =
  member __.Return(x) = Some x
  member __.Zero() = None
  member __.Delay(f) = f (* ここでは実行せず、渡された関数をそのまま返す *)
  member __.Combine(x, rest) =
    match x with
    | Some x -> Some x
    | None -> rest () (* xがNoneのときのみ、渡された関数を実行する *)

この場合、Combine のシグネチャは 'a option -> (unit -> 'a option) -> 'a option となり、MSDNに書いてあるシグネチャとは異なるものになります。まぁ、通常のシグネチャと言っている通り、別に必ずその通りにしなければいけないわけではないので、そういうものだと思ってください。横道にそれますが、別に Combine の実装の結果の型を 'a list option にしてしまってもいいのです。変換された結果がコンパイル可能であれば、どんなシグネチャにしても構いません(ただしそういう実装にすると、Combine をネスト出来なくなり、とても使いにくくなりますが)。

さぁではこれで実行してみましょう！

let option = OptionBuilder()

let res =
  option {
    if true then return 10
    printfn "hello"
    return 20
  }

printfn "%A" res

実行結果:

<fun:res@41>

！？！？

res の型が関数になっちゃってますね。これは、Delay を実装するとコンピュテーション式全体も Delay でくるまれるように変換されるのが原因です。上の方でコンピュテーション式の変換結果をこう書きましたが、

let b = option
b.Combine(
  (if true then b.Return(10) else b.Zero()),
  b.Delay(fun () -> printfn "hello"; b.Return(20)))

正しくはこうです。

let b = option
(* 一番外側もDelayされる *)
b.Delay(fun () ->
  b.Combine(
    (if true then b.Return(10) else b.Zero()),
    b.Delay(fun () -> printfn "hello"; b.Return(20))))

最初の Delay の実装では渡された関数を Delay の中で実行していたので問題になりませんでしたが、今回の Delay の実装は渡された関数をそのまま返すため、最終的な結果が関数になってしまうのです。さて困った・・・

Runの実装

この問題は、コンピュテーションビルダーに Run を実装することで解決できます。コンピュテーションビルダーに Run が実装されていると、一番外側の Delay のさらに外側に Run メソッド呼び出しが挟まれます。つまり、このように変換されることになります。

let b = option
b.Run(
  b.Delay(fun () ->
    b.Combine(
      (if true then b.Return(10) else b.Zero()),
      b.Delay(fun () -> printfn "hello"; b.Return(20)))))

Run には Delay の結果が渡されることから、Run の実装をこうすればいいでしょう。

member __.Run(f) = f ()

これで、望みの動きをする OptionBuilder が手に入りました。

いい感じのOptionBuilder

type OptionBuilder () =
  member __.Return(x) = Some x
  member __.Zero() = None
  member __.Delay(f) = f
  member __.Combine(x, rest) =
    match x with
    | Some x -> Some x
    | None -> rest ()
  member __.Run(f) = f ()

あとは Bind や ReturnFrom などを提供していきましょう。

ListBuilder再考

ListBuilder の Combine は OptionBuilder のような考慮は不要なのでしょうか？考えてみましょう。例えば、以下のようなコードはどうなるべきでしょうか？

let xs = list {
  if false then
    printfn "hello"
    yield 10
  yield 20
}

「hello」とは表示されずに、[20] が返ってきてほしいですよね。このコンピュテーション式の変換結果を見てみましょう。

let b = list
b.Delay(fun () ->
  b.Combine(
    (if false then printfn "hello"; b.Yield(10) else b.Zero()),
    b.Delay(fun () -> b.Yield(20))))

このように、printfn は if 式の中にあるため、単純な Delay の実装で何も問題ありません。

let xs = list {
  yield 10
  printfn "hello"
  yield 20
}

この例では、[10; 20] が返ってきてほしいため、やはり printfn も実行されるべきでしょう。これらのことから、ListBuilder は最初の実装で十分、ということになります。 seq を再実装したい場合は最初の実装では不十分ですが、これがなぜかを考えるのは読者への課題としておきましょう。

もう一つのCombine

Combine の通常のシグネチャは、

M<'T> * M<'T> -> M<'T>

または

M<unit> * M<'T> -> M<'T>

でした。しかし、今まで見てきたものはすべて前者の派生形であり、後者は出てきませんでした。後者の第一引数側が unit になるような Combine はどういうときに出てくるのでしょうか？

今までの例の共通点

今まで見てきたのは、list と option でした。この2つの共通点はいくつかありますが、ここではゼロ値を持つ点が重要です。 list の場合は [] (空リスト)が、option の場合は None がゼロ値です。型の定義を見てみると分かりやすいです。

type 'a list =
  | []         (* ゼロ値 *)
  | (::) of 'a * 'a list

type 'a option =
  | None       (* ゼロ値 *)
  | Some of 'a

このように、ゼロ値とそれ以外の場合でデータコンストラクタが別になっているのが分かります。これらゼロ値は、'a がなんであろうが使えます。

さて、ではこのような「ゼロ値」がないような型を考えてみます。

Async

F#で非同期計算を表す型である Async<'T> を見てみます。この型は list や option と違って、データコンストラクタが1つしかありません*3。

(* https://github.com/Microsoft/visualfsharp/blob/2d413fb940aa1677688454c50b8ec05cd3b6f78f/src/fsharp/FSharp.Core/control.fs#L584より *)
[<NoEquality; NoComparison>]
[<CompiledName("FSharpAsync`1")>]
type Async<'T> =
    P of (AsyncParams<'T> -> FakeUnitValue)

そのため、ゼロ値はありません。 (ちなみに、FakeUnitValue は unit がIL的には void に落ちてしまうため末尾最適化の対象にならない(tail. プレフィックスが発行されない)問題を回避するために導入された型であり、unit と思ってもらって構いません)

しかし、AsyncBuilder は Zero メソッドを次のシグネチャで提供しています。

member Zero : unit -> Async<unit>

Async<unit> 型の値はゼロ値ではありません。例えば 'a option の None は実際の型が int option だとしても string option だとしても使えます。ある意味、ジェネリックな値として振る舞うのです。

それに対して、AsyncBuilder の Zero メソッドは Async<'a> ではなく Async<unit> を返します。この Zero メソッドの定義に意味はあるのでしょうか？ Zero 単体ではわかりにくいので、Combine も見てみます。

let sequentialA p1 p2 =
    bindA p1 (fun () -> p2)

(* snip *)

member b.Combine(p1, p2) = sequentialA p1 p2

引数の順番に注意する必要がありますが、なるほど Bind に落ちるんですね。 bindA の第二引数の関数が受け取る型が unit になっている点に注目してください。つまり、p1 の型は Async<unit> である必要があります。 Combine の型が Async<unit> * Async<'T> -> Async<'T> になりました！さらに、Zero メソッドの戻り値の型と Combine の第一引数の型が一致していることから、両者を組み合わせて使えることがわかります。

このように、ゼロ値が用意されていない(できない)型の場合に、M<unit> * M<'T> -> M<'T> というバージョンの Combine を提供すると、便利な場合があります。 Combine の第一引数側を無視して、第二引数側を常に返すようなイメージですね。また、その場合は Zero メソッドは M<unit> 型の値を返すように定義します。

ということで、AsyncBuilder ではこういうコードがコンパイルできます。

async {
  if cond1 then printfn "if1"
  if cond2 then printfn "if2"
  return "str"
}

おぉ、便利っぽい！

ZeroとCombineの罠

ただ、注意点として、このようなコードもコンパイルできてしまいます。

async {
  if true then
    return ()
  return "str"
}

「え、型はどうなってるの？」と思った方、return という単語のイメージに引きずられています。 F#の return は別にコンピュテーション式全体の型を決めるわけではありません。 AsyncBuilder での Combine は、第一引数側を無視して、第二引数側を常に返すようなイメージでした。第一引数側は Async<unit> になっているため、Combine によって無視(厳密には無視しているわけではないが・・・)されて、第二引数側が返されます。直観と反している気はしますが、そういうものです。

展開結果を見ればもう少し納得しやすいかもしれません。

let b = async
b.Delay(fun () ->
  b.Combine(
    (if true then b.Return() else b.Zero()), (* 第一引数側の結果にかかわらず *)
    b.Delay(fun () ->
      b.Return("str"))))                     (* 第二引数側の結果が使われる *)

こういうビルダーを使うときは、return () と書かないほうが無難でしょう。 unit を受け取る Return をオーバーロードして、Obsolete 属性でコンパイルエラーにする、とかできるかもしれませんのでそういうビルダーが作りたくなった際に参考にしてください。

returnできない罠

型の問題ではなく、「え、return したのにその後ろのコードが実行されるの？」と思った方、return という単語のイメージに引きずられています。 F#の return は別にその時点で結果を返すようなものではありません。単にビルダーの Return メソッドが呼び出されるだけであり、Return 自体は実行の流れを制御できません。

AsyncBuilder の Zero メソッドが返す値はゼロ値ではありませんでした。また、Combine の第一引数が Async<unit> に固定されているため、

async {
  if true then
    return "str1" (* ここにstringは置けない。unitである必要がある *)
  return "str2"
}

とは書けません。コンパイルエラーになります。このあたりを解決するために、Stateを使ったり継続を使ったりできるかもしれませんが、Async では未検証です。気になった方は以下のリンク群をどうぞ。

F#のコンピュテーション式を提供するライブラリ事情

yieldとreturnの話でも調べたのですが、現在の状況を調べてみました。調べたのは下記のコードです。

FSharpx.Extras

まず、Delay の実装ですが、これは受け取った関数を実行せずにそのまま返しています。そのため、Combine の中で第二引数を実行することになります。しかし、これを Option.bind にそのまま渡しているため、Combine の第一引数の型が unit option に固定化されてしまっています。せっかく Zero メソッドが 'a option のゼロ値である None を返しているにもかかわらず、これでは宝の持ち腐れです。

ということで、このようなコードのコンパイルが通ってしまいます。

maybe {
  if true then
    return () (* ??? *)
  return 10
}

さらに、Combine の実装が第一引数として unit option を要求するため、下記のコードはコンパイルが通りません。

maybe {
  if true then
    return 10 (* compile error *)
  return 20
}

これでは Zero メソッドの戻り値を None にしている意味が全くありません。

ExtCore

前回調査時は Zero が返す値が Some () でしたが、そこは None に修正されていました。しかし、Combine がオーバーロードされているうえ、シグネチャもおかしい・・・

member Delay: (unit -> 'T option) -> (unit -> 'T option)
member Combine: unit option * 'T option -> 'T option (* 使われないオーバーロード *)
member Combine: unit option * (unit -> 'T option) -> 'T option
  (* 実際はunit optionではなく'Tではないジェネリック型になっているけど、
     Delayの呼び出しが第二引数に渡されるため、実質unitになる *)

Delay の実装が受け取った関数をそのまま返す実装になっているため、最初の Combine のオーバーロードは使われません。しかも、FSharpx.Extras同様に Combine の実装が Bind を呼び出しているため、やはり下記コードはコンパイルできません。

maybe {
  if true then
    return 10 (* compile error *)
  return 20
}

Zero の実装も意味がなく、やはり下記コードはコンパイルが通ってしまいます。

maybe {
  if true then
    return () (* ??? *)
  return 10
}

なかなかの迷走ぶりです。

Visual F# PowerTools

Visual F# PowerToolsが持っている MaybeBuilder は、過去のバージョンのExtCoreからコピーしてきたものです。そのため、Zero が Some () になっており、Delay は渡された関数を実行しており、Combine は unit option * 'T option -> 'T option 版になっています。 Zero と Combine の整合性は取れていますが、ゼロ値を使っていないのが微妙です。また、Delay が実行を遅延しないバージョンなので、副作用と一緒には使えません。

まぁ、この MaybeBuilder はVFPTの内部のみでしか使われない想定のため、それほど問題ではないでしょう。

Basis.Core

最近全然更新してませんが、このライブラリはそもそも巷のライブラリのコンピュテーションビルダーがことごとくダメ実装だったから作ったライブラリなので、これまで見てきたような問題はありません。

(* コンパイルエラー *)
option {
  if true then
    return ()
  return 10
}

(* Some 10 *)
option {
  if true then
    return 10
  return 20
}

ただし、while の中での return できるようにStateを使った実装をしているため、Zero も Combine もこれまで見てきたものとは全然違うシグネチャおよび実装になっています。

member this.Zero() = None, Continue
member this.Combine((x: _ option, cont), rest: unit -> _ option * FlowControl) =
  match cont with
  | Break -> x, Break
  | Continue -> if x.IsSome then x, Break else rest ()

この実装についての話は、(再掲になりますが)下記のURLをどうぞ。

まとめ

Combine を中心にいろいろなことを見ました。

Combine の目的
Combine 実装に絡む Delay の実装2通り
- 単純な Delay の実装の罠
- もう一つの Delay の実装と Run
単純な Delay の実装で十分なケース (ListBuilder)
第一引数として M<unit> を取る Combine について
- ゼロ値について
- ゼロ値がない場合(Async<'T>)の Combine とその罠
  - return () 出来てしまう
  - return x 出来ない
コンピュテーション式を提供するライブラリの Combine
- 大体のライブラリが何かしら問題を抱えている

皆さんがコンピュテーションビルダーを書く場合で、Combine を提供したくなったときにこのエントリを思い出していただければありがたいです。いやぁ、コンピュテーション式は楽しいなぁ。

*1:セミコロンは改行とインデントで置き換え可能

*2:一部意図的に間違っていますが、そのあたりは後述します

*3:さらに、シグネチャファイルによってただ一つのデータコンストラクタも外部には隠ぺいされている