Applicative Computation Expressions

この記事は、F# Advent Calendar 2020の7日目の記事です。初日の記事であるF# 5.0の新機能でも触れられていますが、 コンピュテーション式でApplicativeな計算を扱えるようにして、より効率的にコンピュテーション式の処理をチューニングすることができる Applicative Computation Expressions について、少しだけ掘り下げてみようと思います。

Optionモナドのコンピュテーション式

まず、手ごろなサンプルとしてOptionモナドのコンピュテーション式の挙動をみてみましょう。

type OptionBuilder1 () =
  member __.Bind(x, f) = 
    printfn "%s" $"{nameof(OptionBuilder1)}:Bind x:{x}"
    Option.bind f x
  member __.Return(x) = 
    printfn "%s" $"{nameof(OptionBuilder1)}:Return x:{x}"
    Some x
    
let option1 = OptionBuilder1()

let option1_1 = option1 { 
  let! v1 = Some 5
  let! v2 = Some 9
  let! v3 = Some 1
  return v1 + v2 + v3
}
//イメージ
//   option1.Return(
//     option1.Bind(Some 5, (fun v1 ->
//       option1.Bind(Some 9, (fun v2 ->
//         option1.Bind(Some 1, (fun (v1, v2, v3) -> v1 + v2 + v3))) 
option1_1 |> printfn "%A"

実行結果

OptionBuilder1:Bind x:Some(5)
OptionBuilder1:Bind x:Some(9)
OptionBuilder1:Bind x:Some(1)
OptionBuilder1:Return x:15
Some 15

Bindが3回呼ばれ、Returnが1回呼ばれて最終的な計算結果のSome 15が得られています。従来のコンピュテーション式では、このように単純な処理の蓄積に対して関数を適用するだけの計算（Applicative）をするケースであっても、何度もBindが呼びだされてしまうという冗長さがありました。コンピュテーション式の文脈の計算はユーザーが期待するよりも比較的コストの高いものでした。この課題を解決するために取り入れられたのが、Applicative Computation Expressionsということになります。

BindReturnとMergeSources

Optionモナドのコンピュテーション式で、Applicative をサポートしてみましょう。Applicative をサポートするために BindReturn とMergeSourcesの実装を検討することができます（どちらか一方だけでもある一定の効果はあります）。

type OptionBuilder2 () =
  member __.Bind(x, f) = 
    printfn "%s" $"{nameof(OptionBuilder2)}:Bind x:{x}"
    Option.bind f x
  member __.Return(x) = 
    printfn "%s" $"{nameof(OptionBuilder2)}:Return x:{x}"
    Some x
  member __.BindReturn(x, f) = 
    printfn "%s" $"{nameof(OptionBuilder2)}:BindReturn x:{x}"
    Option.map f x
  member __.MergeSources(x1, x2) = 
    printfn "%s" $"{nameof(OptionBuilder2)}:MergeSources x1:{x1}, x2:{x2}"
    Option.map2 (fun x y -> (x, y)) x1 x2

let option2 = OptionBuilder2()

Applicativeな計算を適用する場合は、and!(AND BUNG)を適用します。

let otpion2_1 = option2 { 
  let! v1 = Some 5
  and! v2 = Some 9
  return v1 + v2
}
//イメージ
//   option2.BindReturn(
//     option2.MergeSources(Some 5, Some 9, (fun (v1, v2) -> Some (v1 , v2)),
//       fun (v1, v2) -> v1 + v2)
otpion2_1 |> printfn "%A"

実行結果

OptionBuilder2:MergeSources x1:Some(5), x2:Some(9)
OptionBuilder2:BindReturn x:Some((5, 9))
Some 14

BindReturnが実装されている場合、可能な限りより効率的に計算されるようにBindReturnが呼び出されるようにコンパイルされます。この場合、BindとReturnは呼び出されていませんね。

let otpion2_2 = option2 { 
  let! v1 = Some 5
  and! v2 = Some 9
  and! v3 = Some 1
  return v1 + v2 + v3
}
//イメージ
//   option2.BindReturn(
//     option2.MergeSources(Some 5, 
//       option2.MergeSources(Some 9, Some 1, (fun (v2, v3) -> (v2 , v3)),
//          (fun v1 , (v2, v3) ->  (v1 , (v2, v3))),
//             fun (v1, (v2, v3)) -> v1 + v2 + v3)
otpion2_2 |> printfn "%A"

実行結果

OptionBuilder2:MergeSources x1:Some(9), x2:Some(1)
OptionBuilder2:MergeSources x1:Some(5), x2:Some((9, 1))
OptionBuilder2:BindReturn x:Some((5, (9, 1)))
Some 15

結果を蓄積するのに必要な回数ぶんMergeSourcesが呼び出されていることがわかります。

OptionBuilder2のBindReturnをコメントアウトして実行してみるとどうでしょう。

実行結果

OptionBuilder2:MergeSources x1:Some(5), x2:Some(9)
OptionBuilder2:Bind x:Some((5, 9))
OptionBuilder2:Return x:14
Some 14
OptionBuilder2:MergeSources x1:Some(9), x2:Some(1)
OptionBuilder2:MergeSources x1:Some(5), x2:Some((9, 1))
OptionBuilder2:Bind x:Some((5, (9, 1)))
OptionBuilder2:Return x:15
Some 15

というように、BindReturnの代わりにBindとReturnがそれぞれ独立して呼び出されるようになります。

BindNReturn と MergeSourcesN

より効率的にBindReturnとMergeSourcesを計算できるようにパフォーマンスチューニングするための仕組みが用意されています。次の例をみてみましょう。

BindNReturn

BindReturnの他に、Bind2Return、Bind3Return、Bind4Returnを実装します。

type OptionBuilder3 () =
  member __.BindReturn(x, f) = 
    printfn "%s" $"{nameof(OptionBuilder3)}:BindReturn x:{x}"
    Option.map f x
  member this.Bind2Return(x1, x2, f) = 
    printfn "%s" $"{nameof(OptionBuilder3)}:Bind2Return x1:{x1}, x2:{x2}"
    Option.map2 (fun a b -> f (a,b)) x1 x2
  member __.Bind3Return(x1, x2, x3, f) = 
    printfn "%s" $"{nameof(OptionBuilder3)}:Bind3Return x1:{x1}, x2:{x2}, x3:{x3}"
    Option.map3 (fun a b c -> f (a, b, c)) x1 x2 x3
  member __.Bind4Return(x1, x2, x3, x4, f) = 
    printfn "%s" $"{nameof(OptionBuilder3)}:Bind4Return x1:{x1}, x2:{x2}, x3:{x3}, x4:{x4}"
    let map4 f x1 x2 x3 x4 =
      match x1, x2, x3, x4 with
      | Some x1, Some x2, Some x3, Some x4 -> Some (f x1 x2 x3 x4)
      | _, _, _, _ -> None 
    map4 (fun x1 x2 x3 x4 -> f (x1, x2, x3, x4)) x1 x2 x3 x4

let option3 = OptionBuilder3()

つかってみます

let option3_1 = option3 { 
  let! v1 = Some 5
  and! v2 = Some 9
  return v1 + v2
}
//イメージ
// option3.Bind2Return(Some 5, Some 9, (fun (v1, v2) -> v1 + v2))
option3_1 |> printfn "%A"

実行結果

OptionBuilder3:Bind2Return x1:Some(5), x2:Some(9)
Some 14

2つの蓄積した値をつかってmap2の処理をする場合は、Bind2Returnが呼び出されています。

let option3_2 = option3 { 
  let! v1 = Some 5
  and! v2 = Some 9
  and! v3 = Some 10
  return v1 + v2 - v3
}
//イメージ
// option3.Bind3Return(Some 5, Some 9, Some 10, (fun (v1, v2, v3) -> v1 + v2 - v3))
option3_2 |> printfn "%A"

実行結果

OptionBuilder3:Bind3Return x1:Some(5), x2:Some(9), x3:Some(10)
Some 4

3つの蓄積した値をつかってmap3の処理をする場合は、Bind3Returnが呼び出されています。

let option3_3 = option3 { 
  let! v1 = Some 5
  and! v2 = Some 9
  and! v3 = Some 1
  and! v4 = Some 10
  return v1 + v2 + v3 - v4
}
//イメージ
// option3.Bind4Return(Some 5, Some 9, Some 1, Some 10, (fun (v1, v2, v3, v4) -> v1 + v2 + v3 + v4))
option3_3 |> printfn "%A"

実行結果

OptionBuilder3:Bind4Return x1:Some(5), x2:Some(9), x3:Some(1), x4:Some(10)
Some 5

はい。おわかりのとり、4つの蓄積した値をつかってmap4の処理をする場合は、Bind4Returnが呼び出されています。

BindNReturnのNの部分は計算結果の蓄積対象の長さ（個数）に応じて個別に実装可能になっており、パフォーマンスを意識してより細かなチューニングが必要な場合に利用することができます。

BindNReturnについて、F# の実装的には↓このあたりですね。

https://github.com/dotnet/fsharp/blob/77bcbe73861a9e5d3039e6805e0ce144028eae1f/src/fsharp/CheckComputationExpressions.fs#L1160

fsharpより引用

let bindReturnNName = "Bind"+string numSources+"Return"

MergeSourcesN

MergeSourcesについても、BindReturnと同様により細かなチューニングができるようになっています。

type OptionBuilder4 () =
  member __.Bind(x, f) = 
    printfn "%s" $"{nameof(OptionBuilder4)}:Bind x:{x}"
    Option.bind f x
  member __.Return(x) = 
    printfn "%s" $"{nameof(OptionBuilder4)}:Return x:{x}"
    Some x
  member __.BindReturn(x, f) = 
    printfn "%s" $"{nameof(OptionBuilder4)}:BindReturn x:{x}"
    Option.map f x
  member __.MergeSources(x1, x2) = 
    printfn "%s" $"{nameof(OptionBuilder4)}:MergeSources x1:{x1}, x2:{x2}"
    Option.map2 (fun x y -> (x, y)) x1 x2
  member __.MergeSources3(x1, x2, x3) = 
    printfn "%s" $"{nameof(OptionBuilder4)}:MergeSources3 x1:{x1}, x2:{x2}, x3:{x3}"
    Option.map3 (fun x1 x2 x3 -> (x1, x2, x3)) x1 x2 x3
  member __.MergeSources4(x1, x2, x3, x4) =
    printfn "%s" $"{nameof(OptionBuilder4)}:MergeSources4 x1:{x1}, x2:{x2}, x3:{x3}, x4:{x4}"
    let map4 f x1 x2 x3 x4 =
      match x1, x2, x3, x4 with
      | Some x1, Some x2, Some x3, Some x4 -> Some (f x1 x2 x3 x4)
      | _, _, _, _ -> None 
    map4 (fun x1 x2 x3 x4 -> (x1, x2, x3, x4)) x1 x2 x3 x4

let option4 = OptionBuilder4()

つかってみます

let option4_1 = option4 { 
  let! v1 = Some 5
  and! v2 = Some 9
  return v1 + v2
}
//イメージ
//   option4.BindReturn(
//     option4.MergeSources(Some 5, Some 9, (fun (v1, v2) -> Some (v1 , v2)),
//       fun (v1, v2) -> v1 + v2)
option4_1 |> printfn "%A"

実行結果

OptionBuilder3:MergeSources x1:Some(5), x2:Some(9)
OptionBuilder3:BindReturn x:Some((5, 9))
Some 14

2つの値を蓄積する場合には、MergeSourcesが呼ばれます。

let option4_2 = option4 { 
  let! v1 = Some 5
  and! v2 = Some 9
  and! v3 = Some 1
  return v1 + v2 + v3
}
//イメージ
//   option4.BindReturn(
//     option4.MergeSources3(Some 5, Some 9, Some 1, 
//       (fun (v1, v2, v3) -> v1 + v2 + v3)))
option4_2 |> printfn "%A"

実行結果

OptionBuilder4:MergeSources3 x1:Some(5), x2:Some(9), x3:Some(1)
OptionBuilder4:BindReturn x:Some((5, 9, 1))
Some 15

3つの値を蓄積する場合はMergeSources3が呼ばれます。

let option4_3 = option4 { 
  let! v1 = Some 5
  and! v2 = Some 9
  and! v3 = Some 1
  and! v4 = Some 8
  return v1 + v2 + v3 - v4
}
//イメージ
//   option4.BindReturn(
//     option4.MergeSources4(Some 5, Some 9, Some 1, Some 8, 
//       (fun (v1, v2, v3, v4) -> v1 + v2 + v3 - v4)))
option4_3 |> printfn "%A"

実行結果

OptionBuilder4:MergeSources4 x1:Some(5), x2:Some(9), x3:Some(1), x4:Some(8)
OptionBuilder4:BindReturn x:Some((5, 9, 1, 8))
Some 7

もうおわかりですね。4つの値を蓄積する場合はMergeSources4が呼ばれます。

では、MergeSources4をコメントアウトしてoption4_3実行してみるとどうなるでしょう

実行結果例

OptionBuilder4:MergeSources x1:Some(1), x2:Some(8)
OptionBuilder4:MergeSources3 x1:Some(5), x2:Some(9), x3:Some((1, 8))
OptionBuilder4:BindReturn x:Some((5, 9, (1, 8)))
Some 7

MergeSourcesとMergeSources3を組み合わせて4つの値を蓄積するように効率的に計算がなされるようコンパイルしてくれます。MergeSources2を2回呼び出すというような仕組みにはなっていないことがわかります。

実装的には↓このあたりですね。Nが最大のMergeSourcesNを優先して使うようになっているようです。

https://github.com/dotnet/fsharp/blob/77bcbe73861a9e5d3039e6805e0ce144028eae1f/src/fsharp/CheckComputationExpressions.fs#L1197-L1204

fsharpより引用

let maxMergeSources =
    let rec loop (n: int) = 
        let mergeSourcesName = mkMergeSourcesName n
        if isNil (TryFindIntrinsicOrExtensionMethInfo ResultCollectionSettings.AtMostOneResult cenv env bindRange ad mergeSourcesName builderTy) then
            (n-1)
        else
            loop (n+1)
    loop 2

if maxMergeSources = 1 then error(Error(FSComp.SR.tcRequireMergeSourcesOrBindN(bindNName), bindRange))

https://github.com/dotnet/fsharp/blob/77bcbe73861a9e5d3039e6805e0ce144028eae1f/src/fsharp/CheckComputationExpressions.fs#L1194-L1195

fsharpより引用

// Look for the maximum supported MergeSources, MergeSources3, ... 
let mkMergeSourcesName n = if n = 2 then "MergeSources" else "MergeSources"+(string n)

また、上記のようになっていて、2つの値を蓄積する場合にはMergeSources2という名前にならないようにしていることがわかります。

おまけ１：Applicative とは

誤解を恐れずにかみ砕いて言えば、「箱の中の値に対して関数を適用できるのがFunctor」で「箱の中の値に対して箱の中の関数を適用できるのがApplicative」だよ、ということができるかと思います。

まず、箱の中の値に関数を適用する例のやつ、mapを見てみましょう。

//箱の中の値に、関数を適用するやつ。map
let r = Option.map (fun x -> string (x + 10)) (Some 90)
r |> printfn "%A" // "100"

では次に、箱の中の値に、箱の中の関数を適用することを段階的に考えてみます。

//箱の中の値に、箱の中の関数を適用することを考える
let step1 f = Some f
let step2 (a : ('a -> 'b) option) (b : 'a option) : 'b option = 
  match a, b with
  | Some f, Some x -> Some (f x)
  | _ -> None

//箱の中に関数を入れるよ
let r1 = step1 (fun x -> string (x + 10))
//箱の中の値に、箱の中の関数を適用するよ
let r2 = step2 r1 (Some 90)
r2 |> printfn "%A" // "100"

//組み合わせるとこう
let r' = step2 (step1 (fun x -> string (x + 10))) (Some 90)
r' |> printfn "%A" // "100"

step2にあたるのが、Applicativeの操作ですね。

次に、２つの箱の中の値に関数を適用するmap2について見てみましょう。

//２つの箱の中の値に関数を適用するやつ
let r4 = Option.map2 ( * ) (Some 6) (Some 8)
r4 |> printfn "%A" //48

//２つの箱の中の値に、箱の中の関数を適用するやつ
let r4'  = 
  let r4_1 = step2 (step1 (*)) (Some 6)
  step2 r4_1 (Some 8)
r4' |> printfn "%A" //48

以上を踏まえると、Applicativeであるstep2は、Option.map2をつかって次のように表現することができることがわかります。

let step2 g x = Option.map2 id g x

mapNを量産してみよう

Bind4RetrunおよびMergeSources4の実装例では、Option.map4を以下のように愚直に実装しました。が、Nの数が大きくなると愚直に実装するのも骨が折れてしまいますので、効率よく実装してみることを考えてみます。

let map4 f x1 x2 x3 x4 =
  match x1, x2, x3, x4 with
  | Some x1, Some x2, Some x3, Some x4 -> Some (f x1 x2 x3 x4)
  | _, _, _, _ -> None 
map4 (fun x1 x2 x3 x4 -> (x1, x2, x3, x4)) x1 x2 x3 x4

箱の中の関数を、箱の中の値に適用できるApplicativeを利用すると、以下のように表現することができるでしょう。

module Option = 
  let inline (<!>) f x = Option.map f x
  let inline (<*>) g x = Option.map2 id g x

  let map4 f x1 x2 x3 x4 = f <!> x1 <*> x2 <*> x3 <*> x4
  let map5 f x1 x2 x3 x4 x5 = f <!> x1 <*> x2 <*> x3 <*> x4 <*> x5
  let map6 f x1 x2 x3 x4 x5 x6 = f <!> x1 <*> x2 <*> x3 <*> x4 <*> x5 <*> x6
  let map7 f x1 x2 x3 x4 x5 x6 x7 = f <!> x1 <*> x2 <*> x3 <*> x4 <*> x5 <*> x6 <*> x7
  let map8 f x1 x2 x3 x4 x5 x6 x7 x8 = f <!> x1 <*> x2 <*> x3 <*> x4 <*> x5 <*> x6 <*> x7 <*> x8

よかったね。

おまけ２：Bind100Returnしてみる

//なんか重たい処理
let heavyProcess () =
  //0.01secかかるなんか重たい処理😇
  async { do! Async.Sleep(10) } 
  |> Async.RunSynchronously
  
type OptionBuilder1 () =
  member __.Bind (x, f) = 
    //Bindが重たい処理だったと仮定して
    heavyProcess ()
    Option.bind f x
  member __.Return (x) = Some x

let option1 = OptionBuilder1()

type OptionBuilder2 () =
  member __.BindReturn(x, f) = 
    //BindReturn（のうちのBind）が重たい処理だったと仮定して
    heavyProcess ()
    Option.map f x
  member __.MergeSources(x1, x2) =  
    //MergeSourcesの処理も重たい場合は、高コストになるよ
    //heavyProcess ()
    Option.map2 (fun x y -> (x, y)) x1 x2

let option2 = OptionBuilder2()

type OptionBuilder5 () =
  member __.Bind100Return (x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34, x35, x36, x37, x38, x39, x40, x41, x42, x43, x44, x45, x46, x47, x48, x49, x50, x51, x52, x53, x54, x55, x56, x57, x58, x59, x60, x61, x62, x63, x64, x65, x66, x67, x68, x69, x70, x71, x72, x73, x74, x75, x76, x77, x78, x79, x80, x81, x82, x83, x84, x85, x86, x87, x88, x89, x90, x91, x92, x93, x94, x95, x96, x97, x98, x99, x100, f) = 
    //BindReturn（のうちのBind）が重たい処理だったと仮定して
    heavyProcess ()
    Option.map100 (fun x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 x21 x22 x23 x24 x25 x26 x27 x28 x29 x30 x31 x32 x33 x34 x35 x36 x37 x38 x39 x40 x41 x42 x43 x44 x45 x46 x47 x48 x49 x50 x51 x52 x53 x54 x55 x56 x57 x58 x59 x60 x61 x62 x63 x64 x65 x66 x67 x68 x69 x70 x71 x72 x73 x74 x75 x76 x77 x78 x79 x80 x81 x82 x83 x84 x85 x86 x87 x88 x89 x90 x91 x92 x93 x94 x95 x96 x97 x98 x99 x100    -> f (x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34, x35, x36, x37, x38, x39, x40, x41, x42, x43, x44, x45, x46, x47, x48, x49, x50, x51, x52, x53, x54, x55, x56, x57, x58, x59, x60, x61, x62, x63, x64, x65, x66, x67, x68, x69, x70, x71, x72, x73, x74, x75, x76, x77, x78, x79, x80, x81, x82, x83, x84, x85, x86, x87, x88, x89, x90, x91, x92, x93, x94, x95, x96, x97, x98, x99, x100)) x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 x21 x22 x23 x24 x25 x26 x27 x28 x29 x30 x31 x32 x33 x34 x35 x36 x37 x38 x39 x40 x41 x42 x43 x44 x45 x46 x47 x48 x49 x50 x51 x52 x53 x54 x55 x56 x57 x58 x59 x60 x61 x62 x63 x64 x65 x66 x67 x68 x69 x70 x71 x72 x73 x74 x75 x76 x77 x78 x79 x80 x81 x82 x83 x84 x85 x86 x87 x88 x89 x90 x91 x92 x93 x94 x95 x96 x97 x98 x99 x100

let option5 = OptionBuilder5()
  
type OptionBuilder6 () =
  member __.Bind100Return (x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34, x35, x36, x37, x38, x39, x40, x41, x42, x43, x44, x45, x46, x47, x48, x49, x50, x51, x52, x53, x54, x55, x56, x57, x58, x59, x60, x61, x62, x63, x64, x65, x66, x67, x68, x69, x70, x71, x72, x73, x74, x75, x76, x77, x78, x79, x80, x81, x82, x83, x84, x85, x86, x87, x88, x89, x90, x91, x92, x93, x94, x95, x96, x97, x98, x99, x100, f) = 
    //BindReturn（のうちのBind）が重たい処理だったと仮定して
    heavyProcess ()

    //愚直に書いた場合のやつ
    let map100 f x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 x21 x22 x23 x24 x25 x26 x27 x28 x29 x30 x31 x32 x33 x34 x35 x36 x37 x38 x39 x40 x41 x42 x43 x44 x45 x46 x47 x48 x49 x50 x51 x52 x53 x54 x55 x56 x57 x58 x59 x60 x61 x62 x63 x64 x65 x66 x67 x68 x69 x70 x71 x72 x73 x74 x75 x76 x77 x78 x79 x80 x81 x82 x83 x84 x85 x86 x87 x88 x89 x90 x91 x92 x93 x94 x95 x96 x97 x98 x99 x100 =
      match x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34, x35, x36, x37, x38, x39, x40, x41, x42, x43, x44, x45, x46, x47, x48, x49, x50, x51, x52, x53, x54, x55, x56, x57, x58, x59, x60, x61, x62, x63, x64, x65, x66, x67, x68, x69, x70, x71, x72, x73, x74, x75, x76, x77, x78, x79, x80, x81, x82, x83, x84, x85, x86, x87, x88, x89, x90, x91, x92, x93, x94, x95, x96, x97, x98, x99, x100 with
      | Some x1,Some x2,Some x3,Some x4,Some x5,Some x6,Some x7,Some x8,Some x9,Some x10,Some x11,Some x12,Some x13,Some x14,Some x15,Some x16,Some x17,Some x18,Some x19,Some x20,Some x21,Some x22,Some x23,Some x24,Some x25,Some x26,Some x27,Some x28,Some x29,Some x30,Some x31,Some x32,Some x33,Some x34,Some x35,Some x36,Some x37,Some x38,Some x39,Some x40,Some x41,Some x42,Some x43,Some x44,Some x45,Some x46,Some x47,Some x48,Some x49,Some x50,Some x51,Some x52,Some x53,Some x54,Some x55,Some x56,Some x57,Some x58,Some x59,Some x60,Some x61,Some x62,Some x63,Some x64,Some x65,Some x66,Some x67,Some x68,Some x69,Some x70,Some x71,Some x72,Some x73,Some x74,Some x75,Some x76,Some x77,Some x78,Some x79,Some x80,Some x81,Some x82,Some x83,Some x84,Some x85,Some x86,Some x87,Some x88,Some x89,Some x90,Some x91,Some x92,Some x93,Some x94,Some x95,Some x96,Some x97,Some x98,Some x99,Some x100 
        -> Some (f ((x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34, x35, x36, x37, x38, x39, x40, x41, x42, x43, x44, x45, x46, x47, x48, x49, x50, x51, x52, x53, x54, x55, x56, x57, x58, x59, x60, x61, x62, x63, x64, x65, x66, x67, x68, x69, x70, x71, x72, x73, x74, x75, x76, x77, x78, x79, x80, x81, x82, x83, x84, x85, x86, x87, x88, x89, x90, x91, x92, x93, x94, x95, x96, x97, x98, x99, x100)))
      | _ -> None 
    map100 f x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 x21 x22 x23 x24 x25 x26 x27 x28 x29 x30 x31 x32 x33 x34 x35 x36 x37 x38 x39 x40 x41 x42 x43 x44 x45 x46 x47 x48 x49 x50 x51 x52 x53 x54 x55 x56 x57 x58 x59 x60 x61 x62 x63 x64 x65 x66 x67 x68 x69 x70 x71 x72 x73 x74 x75 x76 x77 x78 x79 x80 x81 x82 x83 x84 x85 x86 x87 x88 x89 x90 x91 x92 x93 x94 x95 x96 x97 x98 x99 x100

let option6 = OptionBuilder6()

実行時間を計測してみます

実行時間を計測してみる

  let sw = Diagnostics.Stopwatch()
  let duration title f = 
    printfn "%s start..." title
    sw.Start()
    let returnValue = f()
    sw.Stop()
    printfn "%s end..." title
    TimeSpan(sw.ElapsedTicks) |> printfn "%s Elapsed Time: %A" title
    sw.Reset()
    returnValue

  let test1 () = 
    let ce = option1 { 
      let! v1 = Some 1
      let! v2 = Some 2
      let! v3 = Some 3
      let! v4 = Some 4
      let! v5 = Some 5
      let! v6 = Some 6
      let! v7 = Some 7
      let! v8 = Some 8
      let! v9 = Some 9
      let! v10 = Some 10
      let! v11 = Some 11
      let! v12 = Some 12
      let! v13 = Some 13
      let! v14 = Some 14
      let! v15 = Some 15
      let! v16 = Some 16
      let! v17 = Some 17
      let! v18 = Some 18
      let! v19 = Some 19
      let! v20 = Some 20
      let! v21 = Some 21
      let! v22 = Some 22
      let! v23 = Some 23
      let! v24 = Some 24
      let! v25 = Some 25
      let! v26 = Some 26
      let! v27 = Some 27
      let! v28 = Some 28
      let! v29 = Some 29
      let! v30 = Some 30
      let! v31 = Some 31
      let! v32 = Some 32
      let! v33 = Some 33
      let! v34 = Some 34
      let! v35 = Some 35
      let! v36 = Some 36
      let! v37 = Some 37
      let! v38 = Some 38
      let! v39 = Some 39
      let! v40 = Some 40
      let! v41 = Some 41
      let! v42 = Some 42
      let! v43 = Some 43
      let! v44 = Some 44
      let! v45 = Some 45
      let! v46 = Some 46
      let! v47 = Some 47
      let! v48 = Some 48
      let! v49 = Some 49
      let! v50 = Some 50
      let! v51 = Some 51
      let! v52 = Some 52
      let! v53 = Some 53
      let! v54 = Some 54
      let! v55 = Some 55
      let! v56 = Some 56
      let! v57 = Some 57
      let! v58 = Some 58
      let! v59 = Some 59
      let! v60 = Some 60
      let! v61 = Some 61
      let! v62 = Some 62
      let! v63 = Some 63
      let! v64 = Some 64
      let! v65 = Some 65
      let! v66 = Some 66
      let! v67 = Some 67
      let! v68 = Some 68
      let! v69 = Some 69
      let! v70 = Some 70
      let! v71 = Some 71
      let! v72 = Some 72
      let! v73 = Some 73
      let! v74 = Some 74
      let! v75 = Some 75
      let! v76 = Some 76
      let! v77 = Some 77
      let! v78 = Some 78
      let! v79 = Some 79
      let! v80 = Some 80
      let! v81 = Some 81
      let! v82 = Some 82
      let! v83 = Some 83
      let! v84 = Some 84
      let! v85 = Some 85
      let! v86 = Some 86
      let! v87 = Some 87
      let! v88 = Some 88
      let! v89 = Some 89
      let! v90 = Some 90
      let! v91 = Some 91
      let! v92 = Some 92
      let! v93 = Some 93
      let! v94 = Some 94
      let! v95 = Some 95
      let! v96 = Some 96
      let! v97 = Some 97
      let! v98 = Some 98
      let! v99 = Some 99
      let! v100 = Some 100
      return v1 + v2 + v3 + v4 + v5 + v6 + v7 + v8 + v9 + v10 + v11 + v12 + v13 + v14 + v15 + v16 + v17 + v18 + v19 + v20 + v21 + v22 + v23 + v24 + v25 + v26 + v27 + v28 + v29 + v30 + v31 + v32 + v33 + v34 + v35 + v36 + v37 + v38 + v39 + v40 + v41 + v42 + v43 + v44 + v45 + v46 + v47 + v48 + v49 + v50 + v51 + v52 + v53 + v54 + v55 + v56 + v57 + v58 + v59 + v60 + v61 + v62 + v63 + v64 + v65 + v66 + v67 + v68 + v69 + v70 + v71 + v72 + v73 + v74 + v75 + v76 + v77 + v78 + v79 + v80 + v81 + v82 + v83 + v84 + v85 + v86 + v87 + v88 + v89 + v90 + v91 + v92 + v93 + v94 + v95 + v96 + v97 + v98 + v99 + v100
    }
    ce |> printfn "%A"

  let test2 () = 
    let ce = option2 { 
      let! v1 = Some 1
      and! v2 = Some 2
      and! v3 = Some 3
      and! v4 = Some 4
      and! v5 = Some 5
      and! v6 = Some 6
      and! v7 = Some 7
      and! v8 = Some 8
      and! v9 = Some 9
      and! v10 = Some 10
      and! v11 = Some 11
      and! v12 = Some 12
      and! v13 = Some 13
      and! v14 = Some 14
      and! v15 = Some 15
      and! v16 = Some 16
      and! v17 = Some 17
      and! v18 = Some 18
      and! v19 = Some 19
      and! v20 = Some 20
      and! v21 = Some 21
      and! v22 = Some 22
      and! v23 = Some 23
      and! v24 = Some 24
      and! v25 = Some 25
      and! v26 = Some 26
      and! v27 = Some 27
      and! v28 = Some 28
      and! v29 = Some 29
      and! v30 = Some 30
      and! v31 = Some 31
      and! v32 = Some 32
      and! v33 = Some 33
      and! v34 = Some 34
      and! v35 = Some 35
      and! v36 = Some 36
      and! v37 = Some 37
      and! v38 = Some 38
      and! v39 = Some 39
      and! v40 = Some 40
      and! v41 = Some 41
      and! v42 = Some 42
      and! v43 = Some 43
      and! v44 = Some 44
      and! v45 = Some 45
      and! v46 = Some 46
      and! v47 = Some 47
      and! v48 = Some 48
      and! v49 = Some 49
      and! v50 = Some 50
      and! v51 = Some 51
      and! v52 = Some 52
      and! v53 = Some 53
      and! v54 = Some 54
      and! v55 = Some 55
      and! v56 = Some 56
      and! v57 = Some 57
      and! v58 = Some 58
      and! v59 = Some 59
      and! v60 = Some 60
      and! v61 = Some 61
      and! v62 = Some 62
      and! v63 = Some 63
      and! v64 = Some 64
      and! v65 = Some 65
      and! v66 = Some 66
      and! v67 = Some 67
      and! v68 = Some 68
      and! v69 = Some 69
      and! v70 = Some 70
      and! v71 = Some 71
      and! v72 = Some 72
      and! v73 = Some 73
      and! v74 = Some 74
      and! v75 = Some 75
      and! v76 = Some 76
      and! v77 = Some 77
      and! v78 = Some 78
      and! v79 = Some 79
      and! v80 = Some 80
      and! v81 = Some 81
      and! v82 = Some 82
      and! v83 = Some 83
      and! v84 = Some 84
      and! v85 = Some 85
      and! v86 = Some 86
      and! v87 = Some 87
      and! v88 = Some 88
      and! v89 = Some 89
      and! v90 = Some 90
      and! v91 = Some 91
      and! v92 = Some 92
      and! v93 = Some 93
      and! v94 = Some 94
      and! v95 = Some 95
      and! v96 = Some 96
      and! v97 = Some 97
      and! v98 = Some 98
      and! v99 = Some 99
      and! v100 = Some 100
      return v1 + v2 + v3 + v4 + v5 + v6 + v7 + v8 + v9 + v10 + v11 + v12 + v13 + v14 + v15 + v16 + v17 + v18 + v19 + v20 + v21 + v22 + v23 + v24 + v25 + v26 + v27 + v28 + v29 + v30 + v31 + v32 + v33 + v34 + v35 + v36 + v37 + v38 + v39 + v40 + v41 + v42 + v43 + v44 + v45 + v46 + v47 + v48 + v49 + v50 + v51 + v52 + v53 + v54 + v55 + v56 + v57 + v58 + v59 + v60 + v61 + v62 + v63 + v64 + v65 + v66 + v67 + v68 + v69 + v70 + v71 + v72 + v73 + v74 + v75 + v76 + v77 + v78 + v79 + v80 + v81 + v82 + v83 + v84 + v85 + v86 + v87 + v88 + v89 + v90 + v91 + v92 + v93 + v94 + v95 + v96 + v97 + v98 + v99 + v100
    }
    ce |> printfn "%A"

  let test3 () = 
    let ce = option5 { 
      let! v1 = Some 1
      and! v2 = Some 2
      and! v3 = Some 3
      and! v4 = Some 4
      and! v5 = Some 5
      and! v6 = Some 6
      and! v7 = Some 7
      and! v8 = Some 8
      and! v9 = Some 9
      and! v10 = Some 10
      and! v11 = Some 11
      and! v12 = Some 12
      and! v13 = Some 13
      and! v14 = Some 14
      and! v15 = Some 15
      and! v16 = Some 16
      and! v17 = Some 17
      and! v18 = Some 18
      and! v19 = Some 19
      and! v20 = Some 20
      and! v21 = Some 21
      and! v22 = Some 22
      and! v23 = Some 23
      and! v24 = Some 24
      and! v25 = Some 25
      and! v26 = Some 26
      and! v27 = Some 27
      and! v28 = Some 28
      and! v29 = Some 29
      and! v30 = Some 30
      and! v31 = Some 31
      and! v32 = Some 32
      and! v33 = Some 33
      and! v34 = Some 34
      and! v35 = Some 35
      and! v36 = Some 36
      and! v37 = Some 37
      and! v38 = Some 38
      and! v39 = Some 39
      and! v40 = Some 40
      and! v41 = Some 41
      and! v42 = Some 42
      and! v43 = Some 43
      and! v44 = Some 44
      and! v45 = Some 45
      and! v46 = Some 46
      and! v47 = Some 47
      and! v48 = Some 48
      and! v49 = Some 49
      and! v50 = Some 50
      and! v51 = Some 51
      and! v52 = Some 52
      and! v53 = Some 53
      and! v54 = Some 54
      and! v55 = Some 55
      and! v56 = Some 56
      and! v57 = Some 57
      and! v58 = Some 58
      and! v59 = Some 59
      and! v60 = Some 60
      and! v61 = Some 61
      and! v62 = Some 62
      and! v63 = Some 63
      and! v64 = Some 64
      and! v65 = Some 65
      and! v66 = Some 66
      and! v67 = Some 67
      and! v68 = Some 68
      and! v69 = Some 69
      and! v70 = Some 70
      and! v71 = Some 71
      and! v72 = Some 72
      and! v73 = Some 73
      and! v74 = Some 74
      and! v75 = Some 75
      and! v76 = Some 76
      and! v77 = Some 77
      and! v78 = Some 78
      and! v79 = Some 79
      and! v80 = Some 80
      and! v81 = Some 81
      and! v82 = Some 82
      and! v83 = Some 83
      and! v84 = Some 84
      and! v85 = Some 85
      and! v86 = Some 86
      and! v87 = Some 87
      and! v88 = Some 88
      and! v89 = Some 89
      and! v90 = Some 90
      and! v91 = Some 91
      and! v92 = Some 92
      and! v93 = Some 93
      and! v94 = Some 94
      and! v95 = Some 95
      and! v96 = Some 96
      and! v97 = Some 97
      and! v98 = Some 98
      and! v99 = Some 99
      and! v100 = Some 100
      return v1 + v2 + v3 + v4 + v5 + v6 + v7 + v8 + v9 + v10 + v11 + v12 + v13 + v14 + v15 + v16 + v17 + v18 + v19 + v20 + v21 + v22 + v23 + v24 + v25 + v26 + v27 + v28 + v29 + v30 + v31 + v32 + v33 + v34 + v35 + v36 + v37 + v38 + v39 + v40 + v41 + v42 + v43 + v44 + v45 + v46 + v47 + v48 + v49 + v50 + v51 + v52 + v53 + v54 + v55 + v56 + v57 + v58 + v59 + v60 + v61 + v62 + v63 + v64 + v65 + v66 + v67 + v68 + v69 + v70 + v71 + v72 + v73 + v74 + v75 + v76 + v77 + v78 + v79 + v80 + v81 + v82 + v83 + v84 + v85 + v86 + v87 + v88 + v89 + v90 + v91 + v92 + v93 + v94 + v95 + v96 + v97 + v98 + v99 + v100
    }
    //Equivalent to
    //  option5.Bind100Return(Some 1, Some 2, ..., Some 100, (fun (v1, v2, ..., v256) -> v1 + v2 + ... + v100))
    ce |> printfn "%A"

  let test4 () =
    let ce = option6 { 
      let! v1 = Some 1
      and! v2 = Some 2
      and! v3 = Some 3
      and! v4 = Some 4
      and! v5 = Some 5
      and! v6 = Some 6
      and! v7 = Some 7
      and! v8 = Some 8
      and! v9 = Some 9
      and! v10 = Some 10
      and! v11 = Some 11
      and! v12 = Some 12
      and! v13 = Some 13
      and! v14 = Some 14
      and! v15 = Some 15
      and! v16 = Some 16
      and! v17 = Some 17
      and! v18 = Some 18
      and! v19 = Some 19
      and! v20 = Some 20
      and! v21 = Some 21
      and! v22 = Some 22
      and! v23 = Some 23
      and! v24 = Some 24
      and! v25 = Some 25
      and! v26 = Some 26
      and! v27 = Some 27
      and! v28 = Some 28
      and! v29 = Some 29
      and! v30 = Some 30
      and! v31 = Some 31
      and! v32 = Some 32
      and! v33 = Some 33
      and! v34 = Some 34
      and! v35 = Some 35
      and! v36 = Some 36
      and! v37 = Some 37
      and! v38 = Some 38
      and! v39 = Some 39
      and! v40 = Some 40
      and! v41 = Some 41
      and! v42 = Some 42
      and! v43 = Some 43
      and! v44 = Some 44
      and! v45 = Some 45
      and! v46 = Some 46
      and! v47 = Some 47
      and! v48 = Some 48
      and! v49 = Some 49
      and! v50 = Some 50
      and! v51 = Some 51
      and! v52 = Some 52
      and! v53 = Some 53
      and! v54 = Some 54
      and! v55 = Some 55
      and! v56 = Some 56
      and! v57 = Some 57
      and! v58 = Some 58
      and! v59 = Some 59
      and! v60 = Some 60
      and! v61 = Some 61
      and! v62 = Some 62
      and! v63 = Some 63
      and! v64 = Some 64
      and! v65 = Some 65
      and! v66 = Some 66
      and! v67 = Some 67
      and! v68 = Some 68
      and! v69 = Some 69
      and! v70 = Some 70
      and! v71 = Some 71
      and! v72 = Some 72
      and! v73 = Some 73
      and! v74 = Some 74
      and! v75 = Some 75
      and! v76 = Some 76
      and! v77 = Some 77
      and! v78 = Some 78
      and! v79 = Some 79
      and! v80 = Some 80
      and! v81 = Some 81
      and! v82 = Some 82
      and! v83 = Some 83
      and! v84 = Some 84
      and! v85 = Some 85
      and! v86 = Some 86
      and! v87 = Some 87
      and! v88 = Some 88
      and! v89 = Some 89
      and! v90 = Some 90
      and! v91 = Some 91
      and! v92 = Some 92
      and! v93 = Some 93
      and! v94 = Some 94
      and! v95 = Some 95
      and! v96 = Some 96
      and! v97 = Some 97
      and! v98 = Some 98
      and! v99 = Some 99
      and! v100 = Some 100
      return v1 + v2 + v3 + v4 + v5 + v6 + v7 + v8 + v9 + v10 + v11 + v12 + v13 + v14 + v15 + v16 + v17 + v18 + v19 + v20 + v21 + v22 + v23 + v24 + v25 + v26 + v27 + v28 + v29 + v30 + v31 + v32 + v33 + v34 + v35 + v36 + v37 + v38 + v39 + v40 + v41 + v42 + v43 + v44 + v45 + v46 + v47 + v48 + v49 + v50 + v51 + v52 + v53 + v54 + v55 + v56 + v57 + v58 + v59 + v60 + v61 + v62 + v63 + v64 + v65 + v66 + v67 + v68 + v69 + v70 + v71 + v72 + v73 + v74 + v75 + v76 + v77 + v78 + v79 + v80 + v81 + v82 + v83 + v84 + v85 + v86 + v87 + v88 + v89 + v90 + v91 + v92 + v93 + v94 + v95 + v96 + v97 + v98 + v99 + v100
    }
    ce |> printfn "%A"

  duration "test1" (fun () -> test1 ())
  duration "test2" (fun () -> test2 ())
  duration "test3" (fun () -> test3 ())
  duration "test4" (fun () -> test4 ())

長いので折りたたんでいます

実行結果例

test1 start...
Some 5050
test1 end...
test1 Elapsed Time: 00:00:01.7286957
test2 start...
Some 5050
test2 end...
test2 Elapsed Time: 00:00:00.4500849
test3 start...
Some 5050
test3 end...
test3 Elapsed Time: 00:00:00.5401737
test4 start...
Some 5050
test4 end...
test4 Elapsed Time: 00:00:00.4529156

OptionモナドのようにBindの処理が軽量な場合はさほど気にする必要がないかもしれませんが、Bindの処理が重たいような場合になにも策を講じていない場合、当然ですがチリツモで激おそプログラムになってしまいますね。まあ、ケースバイケースではありますが、BindReturnとMergeSourcesが適切に実装されていれば、一般的なケースでは十分にApplicative Computation Expressionsの効果を享受することができるのではないでしょうか。それ以上の効率化を求める必要がある場合は、適宜BindNReturnやMergeSourcesNの利用も検討しましょうねという感じかと思います。

ではでは。よいコンピュテーション式ライフを(´･_･`)