ビルダーの実装：Combine

この投稿では、Combineメソッドを使ってコンピュテーション式から複数の値を返す方法を見ていきます。

これまでの経緯

これまでの式ビルダークラスは次のようになっています。

type TraceBuilder() =
    member this.Bind(m, f) =
        match m with
        | None ->
            printfn "Noneとバインド中。終了します。"
        | Some a ->
            printfn "Some(%A)とバインド中。続行します" a
        Option.bind f m

    member this.Return(x) =
        printfn "ラップされていない%Aをオプションとして返します" x
        Some x

    member this.ReturnFrom(m) =
        printfn "オプション(%A)を直接返します" m
        m

    member this.Zero() =
        printfn "Zero"
        None

    member this.Yield(x) =
        printfn "ラップされていない%Aをオプションとしてyieldします" x
        Some x

    member this.YieldFrom(m) =
        printfn "オプション(%A)を直接yieldします" m
        m

// ワークフローのインスタンスを作成
let trace = new TraceBuilder()

このクラスはこれまでうまく機能してきました。しかし、問題に直面しようとしています。

2つの’yield’の問題

以前、yieldがreturnと同じように値を返すのに使えることを見ました。

通常、yieldは1回だけではなく、列挙などのプロセスの異なる段階で値を返すために複数回使われます。試してみましょう。

trace {
    yield 1
    yield 2
    } |> printfn "yieldしてからyieldした結果: %A"

しかし、エラーメッセージが出ます。

This control construct may only be used if the computation expression builder defines a 'Combine' method.

yieldの代わりにreturnを使っても、同じエラーが出ます。

trace {
    return 1
    return 2
    } |> printfn "returnしてからreturnした結果: %A"

この問題は他の文脈でも発生します。たとえば、何かを実行してから値を返したい場合、次のようになります。

trace {
    if true then printfn "hello"
    return 1
    } |> printfn "ifしてからreturnした結果: %A"

ここでも’Combine’メソッドがないという同じエラーメッセージが出ます。

問題の理解

何が起こっているのでしょうか？

理解するために、コンピュテーション式の舞台裏に戻ってみましょう。returnとyieldは実際には一連の継続の最後のステップにすぎないことを見てきました。次のようなイメージです。

Bind(1,fun x ->
   Bind(2,fun y ->
     Bind(x + y,fun z ->
        Return(z)  // または Yield

return（またはyield）をインデントを「リセット」するものと考えることができます。そのため、return/yieldしてから再びreturn/yieldすると、次のようなコードが生成されます。

Bind(1,fun x ->
   Bind(2,fun y ->
     Bind(x + y,fun z ->
        Yield(z)
// 新しい式を開始
Bind(3,fun w ->
   Bind(4,fun u ->
     Bind(w + u,fun v ->
        Yield(v)

しかし、これは実際には次のように簡略化できます。

let value1 = ある式
let value2 = 別の式

言い換えれば、コンピュテーション式に2つの値があるということです。そして明らかな疑問は、これら2つの値をどのように組み合わせてコンピュテーション式全体の単一の結果にするかということです。

これは非常に重要なポイントです。ReturnとYieldはコンピュテーション式から早期に戻るわけではありません。そうではなく、コンピュテーション式全体、最後の波かっこまでが常に評価され、単一の値を生成します。繰り返しますが、コンピュテーション式のすべての部分が常に評価されるのです。ショートサーキットは発生しません。早期に戻って値を返したい場合は、自分でコードを書く必要があります（その方法は後で見ていきます）。

では、差し迫った質問に戻りましょう。2つの式が2つの値をもたらします。これらの複数の値をどのように1つに組み合わせるべきでしょうか？

“Combine”の導入

答えはCombineメソッドを使うことです。このメソッドは2つのラップされた値を受け取り、それらを組み合わせて別のラップされた値を作ります。具体的な動作は私たちが決めることができます。

今回の場合、特にint optionを扱っているので、思いつく単純な実装の1つは、数値を足し合わせることです。各パラメータはもちろんoption（ラップされた型）なので、それらを分解して4つの可能なケースを処理する必要があります。

type TraceBuilder() =
    // 他のメンバーは以前と同じ

    member this.Combine (a,b) =
        match a,b with
        | Some a', Some b' ->
            printfn "%Aと%Aを組み合わせています" a' b'
            Some (a' + b')
        | Some a', None ->
            printfn "%AとNoneを組み合わせています" a'
            Some a'
        | None, Some b' ->
            printfn "Noneと%Aを組み合わせています" b'
            Some b'
        | None, None ->
            printfn "NoneとNoneを組み合わせています"
            None

// 新しいインスタンスを作成
let trace = new TraceBuilder()

テストコードを再度実行してみます。

trace {
    yield 1
    yield 2
    } |> printfn "yieldしてからyieldした結果: %A"

しかし、今度は異なるエラーメッセージが出ます。

This control construct may only be used if the computation expression builder defines a 'Delay' method

Delayメソッドは、コンピュテーション式の評価を必要になるまで遅延させるためのフックです。これについては近々詳しく説明します。今のところ、デフォルトの実装を作成しましょう。

type TraceBuilder() =
    // 他のメンバーは以前と同じ

    member this.Delay(f) =
        printfn "Delay"
        f()

// 新しいインスタンスを作成
let trace = new TraceBuilder()

テストコードを再度実行します。

trace {
    yield 1
    yield 2
    } |> printfn "yieldしてからyieldした結果: %A"

ついにコードが完了します。

Delay
ラップされていない1をオプションとしてyieldします
Delay
ラップされていない2をオプションとしてyieldします
1と2を組み合わせています
yieldしてからyieldした結果: Some 3

ワークフロー全体の結果は、すべてのyieldの合計であるSome 3です。

ワークフローに「失敗」（たとえばNone）がある場合、2番目のyieldは発生せず、全体の結果は代わりにSome 1になります。

trace {
    yield 1
    let! x = None
    yield 2
    } |> printfn "yieldしてからNoneの結果: %A"

2つではなく3つのyieldを持つこともできます。

trace {
    yield 1
    yield 2
    yield 3
    } |> printfn "3回yieldした結果: %A"

結果は予想通りSome 6になります。

yieldとreturnを混ぜて使うこともできます。構文の違いを除けば、全体的な効果は同じです。

trace {
    yield 1
    return 2
    } |> printfn "yieldしてからreturnした結果: %A"

trace {
    return 1
    return 2
    } |> printfn "returnしてからreturnした結果: %A"

シーケンス生成にCombineを使う

数値を足し合わせることはyieldの本来の目的ではありませんが、StringBuilderのように文字列を連結するような場合には同様のアイデアを使うかもしれません。

いいえ、yieldは自然にシーケンス生成の一部として使われます。そして今、Combineを理解したので、前回の「ListBuilder」ワークフローに必要なメソッドを追加できます。

• Combineメソッドは単にリストの連結です。
• Delayメソッドは今のところデフォルトの実装を使えます。

以下が完全なクラスです。

type ListBuilder() =
    member this.Bind(m, f) =
        m |> List.collect f

    member this.Zero() =
        printfn "Zero"
        []

    member this.Yield(x) =
        printfn "ラップされていない%Aをリストとしてyieldします" x
        [x]

    member this.YieldFrom(m) =
        printfn "リスト(%A)を直接yieldします" m
        m

    member this.For(m,f) =
        printfn "For %A" m
        this.Bind(m,f)

    member this.Combine (a,b) =
        printfn "%Aと%Aを組み合わせています" a b
        List.concat [a;b]

    member this.Delay(f) =
        printfn "Delay"
        f()

// ワークフローのインスタンスを作成
let listbuilder = new ListBuilder()

そして、これを使用した例です。

listbuilder {
    yield 1
    yield 2
    } |> printfn "yieldしてからyieldした結果: %A"

listbuilder {
    yield 1
    yield! [2;3]
    } |> printfn "yieldしてからyield!した結果: %A"

そして、forループといくつかのyieldを含むより複雑な例です。

listbuilder {
    for i in ["red";"blue"] do
        yield i
        for j in ["hat";"tie"] do
            yield! [i + " " + j;"-"]
    } |> printfn "for..in..doの結果: %A"

結果は次のようになります。

["red"; "red hat"; "-"; "red tie"; "-"; "blue"; "blue hat"; "-"; "blue tie"; "-"]

for..in..doとyieldを組み合わせることで、組み込みのseq式構文（ただし、seqは遅延評価です）にかなり近づいていることがわかります。

舞台裏で何が起こっているのかを理解するまで、これをしばらく試してみることを強くお勧めします。 上の例からわかるように、yieldを創造的に使って、単純なリストだけでなく、さまざまな不規則なリストを生成できます。

注：Whileについて疑問に思っているかもしれませんが、これは今後の投稿でDelayを見た後まで保留にしています。

“combine”の処理順序

Combineメソッドは2つのパラメータしか持ちません。では、2つ以上の値を組み合わせる場合はどうなるでしょうか？たとえば、次のように4つの値を組み合わせる場合を考えてみましょう。

listbuilder {
    yield 1
    yield 2
    yield 3
    yield 4
    } |> printfn "4回yieldした結果: %A"

出力を見ると、予想通り値が対ごとに組み合わされていることがわかります。

[3]と[4]を組み合わせています
[2]と[3; 4]を組み合わせています
[1]と[2; 3; 4]を組み合わせています
4回yieldした結果: [1; 2; 3; 4]

微妙だが重要な点は、最後の値から始まり「後ろ向き」に組み合わされることです。まず”3”と”4”が組み合わされ、その結果が”2”と組み合わされ、というように進みます。

シーケンス以外のCombine

先ほどの問題例の2つ目では、シーケンスではなく、単に2つの別々の式が連続していました。

trace {
    if true then printfn "hello"  //式1
    return 1                      //式2
    } |> printfn "combineの結果: %A"

これらの式をどのように組み合わせるべきでしょうか？

ワークフローがサポートする概念に応じて、一般的にいくつかの方法があります。

“成功”または”失敗”を持つワークフローのCombineの実装

ワークフローに”成功”や”失敗”の概念がある場合、標準的なアプローチは次のとおりです。

• 最初の式が”成功”（文脈に応じてその意味は異なります）した場合、その値を使います。
• そうでない場合は、2番目の式の値を使います。

この場合、通常Zeroには”失敗”値を使います。

このアプローチは、最初の成功が”勝ち”となり、全体の結果になるような一連の”または”式をチェーンするのに便利です。

if (最初の式を実行)
または (2番目の式を実行)
または (3番目の式を実行)

たとえば、maybeワークフローでは、最初の式がSomeの場合はそれを返し、そうでない場合は2番目の式を返すのが一般的です。次のように実装します。

type TraceBuilder() =
    // 他のメンバーは以前と同じ

    member this.Zero() =
        printfn "Zero"
        None  // 失敗

    member this.Combine (a,b) =
        printfn "%Aと%Aを組み合わせています" a b
        match a with
        | Some _ -> a  // aが成功 -- aを使う
        | None -> b    // aが失敗 -- 代わりにbを使う

// 新しいインスタンスを作成
let trace = new TraceBuilder()

例：パース

この実装を使ったパースの例を試してみましょう。

type IntOrBool = I of int | B of bool

let parseInt s =
    match System.Int32.TryParse(s) with
    | true,i -> Some (I i)
    | false,_ -> None

let parseBool s =
    match System.Boolean.TryParse(s) with
    | true,i -> Some (B i)
    | false,_ -> None

trace {
    return! parseBool "42"  // 失敗
    return! parseInt "42"
    } |> printfn "パースの結果: %A"

次のような結果が得られます。

Some (I 42)

最初のreturn!式がNoneとなり、無視されているのがわかります。そのため、全体の結果は2番目の式であるSome (I 42)になります。

例：辞書検索

この例では、複数の辞書で同じキーを検索し、値が見つかったら返します。

let map1 = [ ("1","One"); ("2","Two") ] |> Map.ofList
let map2 = [ ("A","Alice"); ("B","Bob") ] |> Map.ofList

trace {
    return! map1.TryFind "A"
    return! map2.TryFind "A"
    } |> printfn "マップ検索の結果: %A"

次のような結果が得られます。

マップ検索の結果: Some "Alice"

最初の検索がNoneとなり、無視されているのがわかります。そのため、全体の結果は2番目の検索結果になります。

ご覧のように、この手法はパースや（おそらく失敗する）一連の操作を評価する際に非常に便利です。

順次ステップを持つワークフローのCombineの実装

ワークフローに順次ステップの概念がある場合、全体の結果は単に最後のステップの値となり、それ以前のすべてのステップは副作用のためだけに評価されます。

通常のF#では、これは次のように書かれます。

do some expression
do some other expression
final expression

またはセミコロン構文を使って、単に次のように書きます。

some expression; some other expression; final expression

通常のF#では、各式（最後のものを除く）はunit値に評価されます。

コンピュテーション式の同等のアプローチは、各式（最後のものを除く）をラップされたunit値として扱い、それを次の式に「渡す」ことです。これを最後の式に到達するまで繰り返します。

これはもちろんbindが行うことそのものなので、最も簡単な実装はBindメソッド自体を再利用することです。また、このアプローチが機能するためには、Zeroがラップされたunit値であることが重要です。

type TraceBuilder() =
    // 他のメンバーは以前と同じ

    member this.Zero() =
        printfn "Zero"
        this.Return ()  // None ではなく unit

    member this.Combine (a,b) =
        printfn "%Aと%Aを組み合わせています" a b
        this.Bind( a, fun ()-> b )

// 新しいインスタンスを作成
let trace = new TraceBuilder()

通常のbindとの違いは、継続がunitパラメータを持ち、bに評価されることです。これにより、aは一般的にWrapperType<unit>型、または今回の場合はunit option型になります。

このCombineの実装で動作する順次処理の例を示します。

trace {
    if true then printfn "hello......."
    if false then printfn ".......world"
    return 1
    } |> printfn "順次combineの結果: %A"

以下がトレース結果です。式全体の結果が、通常のF#コードと同様にシーケンスの最後の式の結果になっていることに注目してください。

hello.......
Zero
ラップされていない<null>をオプションとして返します
Zero
ラップされていない<null>をオプションとして返します
ラップされていない1をオプションとして返します
Some nullとSome 1を組み合わせています
Some nullとSome 1を組み合わせています
順次combineの結果: Some 1

データ構造を構築するワークフローのCombineの実装

最後に、ワークフローの別の一般的なパターンは、データ構造を構築することです。この場合、Combineは2つのデータ構造を適切な方法でマージする必要があります。 そして、Zeroメソッドは必要に応じて（そして可能であれば）空のデータ構造を作成する必要があります。

上の「リストビルダー」の例では、まさにこのアプローチを使いました。Combineは単にリストの連結で、Zeroは空のリストでした。

“Combine”と”Zero”を混ぜる際のガイドライン

オプション型に対する2つの異なるCombineの実装を見てきました。

• 1つ目は、オプションを「成功/失敗」の指標として使い、最初の成功が「勝ち」となる場合です。この場合、ZeroはNoneとして定義されました。
• 2つ目は順次的なものでした。この場合、ZeroはSome ()として定義されました。

両方のケースがうまく機能しましたが、これは運が良かっただけでしょうか、それともCombineとZeroを正しく実装するためのガイドラインはあるのでしょうか？

まず、Combineはパラメータを入れ替えても同じ結果を与える必要はありません。 つまり、Combine(a,b)はCombine(b,a)と同じである必要はありません。リストビルダーはこの良い例です。

一方で、ZeroとCombineを結びつける便利なルールがあります。

ルール：Combine(a,Zero)はCombine(Zero,a)と同じであり、これは単にaと同じでなければなりません。

算術からのアナロジーを使うと、Combineを加算のように考えることができます（これは悪いアナロジーではありません - 実際に2つの値を「加算」しているのです）。そしてZeroはもちろん数字のゼロです！したがって、上記のルールは次のように表現できます。

ルール：a + 0は0 + aと同じであり、これは単にaと同じです。ここで+はCombineを、0はZeroを意味します。

オプション型に対する最初のCombine実装（「成功/失敗」）を見ると、このルールに確かに従っていることがわかります。2番目の実装（Some()での「bind」）も同様です。

一方で、「bind」実装のCombineを使いながら、ZeroをNoneとして定義したままにしていた場合、加算ルールに従わないことになり、何かが間違っているというヒントになります。

bindを使わない”Combine”

他のすべてのビルダーメソッドと同様に、必要ない場合は実装する必要はありません。そのため、強く順序付けられたワークフローの場合、BindとReturnを全く実装せずに、Combine、Zero、Yieldだけを持つビルダークラスを簡単に作成できます。

以下は、動作する最小限の実装の例です。

type TraceBuilder() =

    member this.ReturnFrom(x) = x

    member this.Zero() = Some ()

    member this.Combine (a,b) =
        a |> Option.bind (fun ()-> b )

    member this.Delay(f) = f()

// ワークフローのインスタンスを作成
let trace = new TraceBuilder()

そして、これを使用した例です。

trace {
    if true then printfn "hello......."
    if false then printfn ".......world"
    return! Some 1
    } |> printfn "最小限のcombineの結果: %A"

同様に、データ構造指向のワークフローがある場合、Combineといくつかの他のヘルパーだけを実装できます。たとえば、以下はリストビルダークラスの最小限の実装です。

type ListBuilder() =

    member this.Yield(x) = [x]

    member this.For(m,f) =
        m |> List.collect f

    member this.Combine (a,b) =
        List.concat [a;b]

    member this.Delay(f) = f()

// ワークフローのインスタンスを作成
let listbuilder = new ListBuilder()

最小限の実装でも、次のようなコードを書くことができます。

listbuilder {
    yield 1
    yield 2
    } |> printfn "結果: %A"

listbuilder {
    for i in [1..5] do yield i + 2
    yield 42
    } |> printfn "結果: %A"

スタンドアロンの”Combine”関数

前回の投稿で、“bind”関数がしばしばスタンドアロン関数として使用され、通常>>=演算子が与えられることを見ました。

Combine関数も、しばしばスタンドアロン関数として使用されます。bindとは異なり、標準的な記号はありません — combineの動作に応じて異なる場合があります。

対称的な結合操作はしばしば++や<+>と書かれます。 そして、先ほどオプションに使用した「左優先」の結合（つまり、最初の式が失敗した場合にのみ2番目の式を実行する）は、ときに<++と書かれます。

以下は、辞書検索の例で使用したオプションのスタンドアロンの左優先結合の例です。

module StandaloneCombine =

    let combine a b =
        match a with
        | Some _ -> a  // aが成功 -- aを使う
        | None -> b    // aが失敗 -- bを使う

    // 中置バージョンを作成
    let ( <++ ) = combine

    let map1 = [ ("1","One"); ("2","Two") ] |> Map.ofList
    let map2 = [ ("A","Alice"); ("B","Bob") ] |> Map.ofList

    let result =
        (map1.TryFind "A")
        <++ (map1.TryFind "B")
        <++ (map2.TryFind "A")
        <++ (map2.TryFind "B")
        |> printfn "オプションの加算結果: %A"

まとめ

この投稿でCombineについて学んだことは何でしょうか？

• コンピュテーション式で複数のラップされた値を組み合わせたり「加算」したりする必要がある場合、Combine（とDelay）を実装する必要があります。
• Combineは値を対ごとに、最後から最初へと組み合わせます。
• すべてのケースで機能するCombineの普遍的な実装はありません ―― ワークフローの特定のニーズに応じてカスタマイズする必要があります。
• CombineとZeroを関連づける合理的なルールがあります。
• Combineの実装にBindは必要ありません。
• Combineはスタンドアロン関数として公開できます。

次の投稿では、内部式がいつ正確に評価されるかを制御するロジックを追加し、真の短絡評価と遅延評価を導入します。