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
では未検証です。
気になった方は以下のリンク群をどうぞ。
- コンピュテーション式の実装にStateを用いる
- コンピュテーション式におけるreturnとyield
- 継続を使ってOptionコンピュテーション式を実装する
- 継続渡しスタイルを使ってListコンピュテーション式を実装する
- F#のコンピュテーション式
- yieldとreturnの話
F#のコンピュテーション式を提供するライブラリ事情
yieldとreturnの話でも調べたのですが、現在の状況を調べてみました。 調べたのは下記のコードです。
- FSharpx.ExtrasのMonad.fsのMaybeBuilder
- ExtCoreのcontrol.fsのMaybeBuilder
- Visual F# PowerToolsのUtils.fsのMaybeBuilder
- Basis.CoreのComputationExpr.fsのOptionBuilder
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
を提供したくなったときにこのエントリを思い出していただければありがたいです。
いやぁ、コンピュテーション式は楽しいなぁ。