🦥
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# の実装的には↓このあたりですね。
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を優先して使うようになっているようです。
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))
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の利用も検討しましょうねという感じかと思います。
ではでは。よいコンピュテーション式ライフを(´･_･`)
Discussion
効率の他に別の面では、Applicative ではあるが Monad ではないものに対してもコンピュテーション式が使えるようになったということかな