option はデータの有無を表す型ですが、エラー処理にも使うことができます。Result は option を改良した型で、Ok と Error のどちらかにデータを格納することができます。通常は option の None の代わりに Error を使い、Some の代わりに Ok を使います。たとえば、エラーがあったときに Error にエラーを表すデータを入れて返す、という使い方をします。今回は option と Result を使ったエラー処理について簡単に説明します。
option にはコンストラクタ None と Some のほかに、以下に示すプロパティが用意されています。
簡単な例を示しましょう。
> let a = Some 10;; val a: int option = Some 10 > a.IsNone;; val it: bool = false > a.IsSome;; val it: bool = true > a.Value;; val it: int = 10 > let b = None : int option;; val b: int option = None > b.IsNone;; val it: bool = true > b.IsSome;; val it: bool = false > b.Value;; => エラー
モジュール Option には option を操作する便利な関数が用意されています。プロパティに対応する関数を以下に示します。
Option.isNone option => bool Option.isSome option => bool Option.get option => value (None は例外を送出)
このほかにも、option を要素が 0 個または 1 個のコレクションとみなして、リストや配列と同様に操作する関数も用意されています。
> Option.map;;
val it: (('a -> 'b) -> 'a option -> 'b option)
> Option.fold;;
val it: (('a -> 'b -> 'a) -> 'a -> 'b option -> 'a)
> Option.foldBack;;
val it: (('a -> 'b -> 'b) -> 'a option -> 'b -> 'b)
> Option.iter;;
val it: (('a -> unit) -> 'a option -> unit)
> Option.exists;;
val it: (('a -> bool) -> 'a option -> bool)
> Option.forall;;
val it: (('a -> bool) -> 'a option -> bool)
簡単な使用例を示しましょう。
> Some 10 |> Option.map (fun x -> x * x);; val it: int option = Some 100 > None |> Option.map (fun x -> x * x);; val it: int option = None > Option.fold (fun a x -> x::a) [] (Some 10);; val it: int list = [10] > Option.fold (fun a x -> x::a) [] (None: int option);; val it: int list = [] > Option.iter (fun x -> printfn "%d" x) (Some 10);; 10 val it: unit = () > Option.iter (fun x -> printfn "%d" x) (None: int option);; val it: unit = () > Option.exists (fun x -> x % 2 = 0) (Some 10);; val it: bool = true > Option.exists (fun x -> x % 2 = 0) (Some 5);; val it: bool = false > Option.exists (fun x -> x % 2 = 0) None;; val it: bool = false > Option.forall (fun x -> x % 2 = 0) (Some 10);; val it: bool = true > Option.forall (fun x -> x % 2 = 0) (Some 5);; val it: bool = false > Option.forall (fun x -> x % 2 = 0) None;; val it: bool = true
ここで、関数 map に注目してください。option の map はリストの map とよく似ています。
> Option.map;;
val it: (('a -> 'b) -> 'a option -> 'b option)
> List.map;;
val it: (('a -> 'b) -> 'a list -> 'b list)
どちらも最初の引数は関数 'a -> 'b、次の引数がデータを格納する型、最後の返り値は第 2 引数と同じ型です。つまり、型からデータを取り出し、それを関数 'a -> 'b に適用し、その結果を同じ型に格納して返すことがわかります。関数型言語 Haskell では、このような操作を「ファンクタ (Functor)」といいます。
option の map は Some からデータを取り出して、それに関数を適用して返り値を Some に格納して返します。None はデータを格納していないので None をそのまま返します。エラーを表す型を None とすると、option は失敗するかもしれない計算を表している、と考えることができます。
ただし、関数 'a -> 'b でエラーが発生したとき option を返すことにすると、ちょっと困ったことが起きるのです。option を返す関数を map に適用すると、option が二重になってしまうのです。
> Some 1 |> Option.map (fun x -> if x % 2 = 0 then Some x else None);; val it: int option option = Some None > Some 2 |> Option.map (fun x -> if x % 2 = 0 then Some x else None);; val it: int option option = Some (Some 2) > None |> Option.map (fun x -> if x % 2 = 0 then Some x else None);; val it: int option option = None
このため、第 1 引数 (関数) の型を 'a -> 'a option に変更した関数 bind が用意されています。
> Option.bind;;
val it: (('a -> 'b option) -> 'a option -> 'b option)
第 1 引数の関数は計算結果を option に格納して返します。つまり、bind は option から値を取り出し、それを関数に渡して評価し、その返り値をそのまま返す、という働きをします。このような操作を Haskell では「モナド (Monad)」といいます。
簡単な使用例を示しましょう。
> Some 1 |> Option.bind (fun x -> if x % 2 = 0 then Some x else None);; val it: int option = None > Some 2 |> Option.bind (fun x -> if x % 2 = 0 then Some x else None);; val it: int option = Some 2 > None |> Option.bind (fun x -> if x % 2 = 0 then Some x else None);; val it: int option = None
Option.bind の返り値の型は 'b option なので、|> と bind を使って関数を連結していくことができます。簡単な例を示しましょう。
> Some 1 |> Option.bind (fun x -> Some (x * 2)) |> Option.bind (fun x -> Some (x + 10));; val it: int option = Some 12 > None |> Option.bind (fun x -> Some (x * 2)) |> Option.bind (fun x -> Some (x + 10));; val it: int option = None > Some 1 |> Option.bind (fun x -> if x > 10 then None else Some x) - |> Option.bind (fun x -> if x < 0 then None else Some x);; val it: int option = Some 1 > Some 11 |> Option.bind (fun x -> if x > 10 then None else Some x) - |> Option.bind (fun x -> if x < 0 then None else Some x);; val it: int option = None > Some (-1) |> Option.bind (fun x -> if x > 10 then None else Some x) - |> Option.bind (fun x -> if x < 0 then None else Some x);; val it: int option = None
最初の関数は引数 x を 2 倍し、次の関数は引数 x に 10 を加算します。2 つの関数を |> と bind でつなげると、x * 2 + 10 を計算する処理になります。|> の左辺値が None の場合、bind はそれをそのまま返すので、返り値も None になります。関数でエラーが発生して None を返す場合でも、None は伝搬するので最後の値は None になります。
なお、Haskell のファンクタやモナドは数学の「圏論」が由来の機能です。どちらの操作にも満たすべき規則があるのですが、本ページの範囲を超えるので、説明は割愛させていただきます。興味のある方は拙作のページ Haskell 入門 ファンクタ, モナド (2) をお読みくださいませ。
それではここでファンクタとモナドの理解を深めるため、私たちで map と bind を定義してみましょう。型名は Haskell の Maybe を拝借して maybe とします。今回は map と bind をメソッド (Map, Bind) として定義します。プログラムは次のようになります。
リスト : maybe のファンクタとモナド
type 'a maybe =
| Nothing
| Just of 'a
member this.Map(func) =
match this with
Nothing -> Nothing
| Just x -> Just (func x)
member this.Bind(func) =
match this with
Nothing -> Nothing
| Just x -> func x
maybe は None のかわりに Nothing を、Some のかわりに Just を使います。これらの名前も Haskell の Maybe から拝借しました。
Map の場合、this が Nothing であれば Nothing をそのまま返し、Just x であれば Just (func x) を返します。Bind は this が Nothing であれば Nothing を返します。そうでなければ、Just x から値 x を取り出して、関数 func に渡して評価するだけです。
それでは実際に試してみましょう。
> type 'a maybe =
- | Nothing
- | Just of 'a
-
- member this.Map(func) =
- match this with
- Nothing -> Nothing
- | Just x -> Just (func x)
-
- member this.Bind(func) =
- match this with
- Nothing -> Nothing
- | Just x -> func x;;
type 'a maybe =
| Nothing
| Just of 'a
member Bind: func: ('a -> 'a0 maybe) -> 'a0 maybe
member Map: func: ('a -> 'a0) -> 'a0 maybe
> let a = Just 10;;
val a: int maybe = Just 10
> let b = Nothing : int maybe;;
val b: int maybe = Nothing
> a.Map(fun x -> x * 2);;
val it: int maybe = Just 20
> b.Map(fun x -> x * 2);;
val it: int maybe = Nothing
> a.Bind(fun x -> Just(x * 2));;
val it: int maybe = Just 20
> b.Bind(fun x -> Just(x * 2));;
val it: int maybe = Nothing
> (Just 1).Map(fun x -> if x % 2 = 0 then Just x else Nothing);; val it: int maybe maybe = Just Nothing > (Just 2).Map(fun x -> if x % 2 = 0 then Just x else Nothing);; val it: int maybe maybe = Just (Just 2) > Nothing.Map(fun x -> if x % 2 = 0 then Just x else Nothing);; val it: int maybe maybe = Nothing > (Just 1).Bind(fun x -> if x % 2 = 0 then Just x else Nothing);; val it: int maybe = Nothing > (Just 2).Bind(fun x -> if x % 2 = 0 then Just x else Nothing);; val it: int maybe = Just 2 > Nothing.Bind(fun x -> if x % 2 = 0 then Just x else Nothing);; val it: int maybe = Nothing
正常に動作しているようです。興味のある方はいろいろ試してみてください。
次は Result について説明します。Result の定義を示します。
リスト : Result の定義 type Result<'T, 'TError> = Error of 'TError | Ok of 'T
Result は option を改良したデータ型で、Error と Ok のどちらかにデータを格納することができます。Error と Ok の型は異なっていてもかまいません。通常は option の None の代わりに Error を使い、Some の代わりに Ok を使います。たとえば、エラーがあったときに Error にエラーを表すデータを入れて返す、という使い方をします。
簡単な例を示します。
- Ok 10;; val it: Result<int,'a> > Error "oops";; val it: Result<'a,string>
モジュール Result には関数 map と bind が用意されています。
> Result.map;;
val it: (('a -> 'b) -> Result<'a,'c> -> Result<'b,'c>)
> Result.bind;;
val it: (('a -> Result<'b,'c>) -> Result<'a,'c> -> Result<'b,'c>)
簡単な使用例を示しましょう。
> let a = (Ok 10): Result<int,string>;; val a: Result<int,string> = Ok 10 > let b = (Error "oops"): Result<int,string>;; val b: Result<int,string> = Error "oops" > a |> Result.map (fun x -> x * x);; val it: Result<int,string> = Ok 100 > b |> Result.map (fun x -> x * x);; val it: Result<int,string> = Error "oops" > a |> Result.bind (fun x -> Ok (x * x));; val it: Result<int,string> = Ok 100 > b |> Result.bind (fun x -> Ok (x * x));; val it: Result<int,string> = Error "oops" > a |> Result.map (fun x -> if x < 0 then Error "negative" else Ok (x * x));; val it: Result<Result<int,string>,string> = Ok (Ok 100) > a |> Result.bind (fun x -> if x < 0 then Error "negative" else Ok (x * x));; val it: Result<int,string> = Ok 100 > let c = (Ok -1): Result<int,string>;; val c: Result<int,string> = Ok -1 > c |> Result.map (fun x -> if x < 0 then Error "negative" else Ok (x * x));; val it: Result<Result<int,string>,string> = Ok (Error "negative") > c |> Result.bind (fun x -> if x < 0 then Error "negative" else Ok (x * x));; val it: Result<int,string> = Error "negative"
option と同様に、result も |> と bind を使って関数を連結することができます。F# では、これを「Railway 指向プログラミング」と呼ぶようです。簡単な例を示します。
> a |> Result.bind (fun x -> if x < 0 then Error "negative" else Ok (x * x)) - |> Result.bind (fun x -> if x > 100 then Error "over 100" else Ok (x + 100));; val it: Result<int,string> = Ok 200 > c |> Result.bind (fun x -> if x < 0 then Error "negative" else Ok (x * x)) - |> Result.bind (fun x -> if x > 100 then Error "over 100" else Ok (x + 100));; val it: Result<int,string> = Error "negative" > let d = (Ok 11): Result<int,string>;; val d: Result<int,string> = Ok 11 > d |> Result.bind (fun x -> if x < 0 then Error "negative" else Ok (x * x)) - |> Result.bind (fun x -> if x > 100 then Error "over 100" else Ok (x + 100));; val it: Result<int,string> = Error "over 100"
それではここでファンクタとモナドの理解を深めるため、私たちで map と bind を定義してみましょう。型名は Haskell の Either を拝借して either とします。今回は map と bind をメソッド (Map, Bind) として定義します。プログラムは次のようになります。
リスト : either のファンクタとモナド
type either<'a, 'b> =
| Left of 'b
| Right of 'a
member this.Map(func) =
match this with
Left x -> Left x
| Right x -> Right (func x)
member this.Bind(func) =
match this with
Left x -> Left x
| Right x -> func x
either は Error のかわりに Left を、Ok のかわりに Right を使います。これらの名前も Haskell の Either から拝借しました。
Map の場合、this が Left x であれば Left x をそのまま返し、Right x であれば Right (func x) を返します。Bind は this が Left x であれば Left x を返します。そうでなければ、Right x から値 x を取り出して、関数 func に渡して評価するだけです。
それでは実際に試してみましょう。
> type either<'a, 'b> =
- | Left of 'b
- | Right of 'a
-
- member this.Map(func) =
- match this with
- Left x -> Left x
- | Right x -> Right (func x)
-
- member this.Bind(func) =
- match this with
- Left x -> Left x
- | Right x -> func x;;
type either<'a,'b> =
| Left of 'b
| Right of 'a
member Bind: func: ('a -> either<'a0,'b>) -> either<'a0,'b>
member Map: func: ('a -> 'a0) -> either<'a0,'b>
> Left "oops";;
val it: either<'a,string>
> Right 100;;
val it: either<int,'a>
> let a = (Right 10): either<int,string>;;
val a: either<int,string> = Right 10
> let b = (Left "oops"): either<int,string>;;
val b: either<int,string> = Left "oops"
> a.Map(fun x -> x * x);;
val it: either<int,string> = Right 100
> b.Map(fun x -> x * x);;
val it: either<int,string> = Left "oops"
> a.Bind(fun x -> Right(x * x));;
val it: either<int,string> = Right 100
> b.Bind(fun x -> Right(x * x));;
val it: either<int,string> = Left "oops"
> a.Bind(fun x -> Right(x * x)).Bind(fun x -> Right(x + 100));;
val it: either<int,string> = Right 200
> a.Bind(fun x -> Right(x * x)).Bind(fun x -> if x < 100 then Right x else Left "over 99").Bind(
- fun x -> Right(x + 100))
val it: either<int,string> = Left "over 99"
正常に動作しているようです。興味のある方はいろいろ試してみてください。
ファンクタやモナドはリスト List<'a> でも定義することができます。リストのファンクタは List.map そのものです。Haskell の場合、モナドは型によって、Maybe モナド、リストモナド、Either モナドというように、型を付けて呼ばれています。
ここで Option や Result と同様に、空リストは失敗を表していると考えます。空リストの場合は空リストを返します。これは map でもできますが、空リスト以外の場合、返り値のリストが二重になってしまいます。そこで、モナド (bind) に渡す関数の型を次のように定義します。
bind: ('a -> 'b list) -> 'a list -> 'b list
bind の動作は map の結果を平坦化 (concat) したもの、つまり関数 List.collect と同じになります。
> List.collect;;
val it: (('a -> 'b list) -> 'a list -> 'b list)
Haskell では concatMap と呼ばれていいます。List.collect の簡単な使用例を示しましょう。
> List.collect (fun x -> [1..x]) [];; val it: int list = [] > List.collect (fun x -> [1..x]) [1..5];; val it: int list = [1; 1; 2; 1; 2; 3; 1; 2; 3; 4; 1; 2; 3; 4; 5] > List.map (fun x -> [1..x]) [];; val it: int list list = [] > List.map (fun x -> [1..x]) [1..5];; val it: int list list = [[1]; [1; 2]; [1; 2; 3]; [1; 2; 3; 4]; [1; 2; 3; 4; 5]]
map と比較すると、collect の動作がよくわかると思います。
option の None が「失敗」を表すことができるように、リストの空リストも失敗を表すことができます。逆に、ある計算が「成功」した場合、option は結果を Some で表すことができます。リストの場合、複数の要素が格納されているので、どの要素が成功するのかわかりませんが、この中に計算が成功する要素が含まれていると考えます。
そこで、リストの中から要素を一つ選ぶ処理を考えます。たとえば、List.item n ls はリスト ls の n 番目の要素を取り出しますが、選ぶ要素を引数 n で指定する必要があります。これに対して、特別な指定をしないで無作為に要素を選ぶことを考えます。このような選択を「非決定的選択」といいます。
ここで、非決定的選択は問題を解くのに都合のいい選択が行われると仮定します。つまり、複数の選択肢の中で解に導くものがいくつか存在するならば、そのうちの一つを選択するのです。たとえば、迷路で分かれ道にきた場合、その中から出口につながる道を一つ選ぶわけです。このような非決定的選択を含む処理 (計算) を「非決定性計算」とか「非決定性」といいます。
このような都合のいい処理を現在のコンピュータで実現することは不可能ですが、バックトラックを使って近似的に実現することは可能です。つまり、ある要素を選んで条件を満たさない場合は、バックトラックして異なる要素を選択すればいいわけです。リストモナドはすべての組み合わせを生成するように動作するので、その中から条件を満たす解を探せばいいわけです。
このように、リストモナドは「非決定性計算」をシミュレートしていると考えることができます。リストモナドに興味のある方は、拙作のページ Haskell 入門: モナド (1) をお読みくださいませ。
F# のモジュール List に関数 bind は用意されていませんが、「型拡張」という機能を使うと既存の型にメソッドを追加することができます。型拡張の構文を示します。
type 型名 with member 自己修飾子.メソッド名(引数, ...) = 式
type 型名 with のあとにメソッドを定義するだけです。これで型 (クラスやレコードなど) に新しいメソッドを追加することができます。ただし、型拡張で演算子を多重定義 (オーバーロード) することはできません。ご注意くださいませ。
それでは実際に試してみましょう。
> type List<'a> with
- member this.bind f = List.collect f this;;
type List<'T> with
member bind: f: ('T -> 'a list) -> 'a list
> [1..5].bind(fun x -> [x * 2]);;
val it: int list = [2; 4; 6; 8; 10]
> [1..5].bind(fun x -> [1..x]);;
val it: int list = [1; 1; 2; 1; 2; 3; 1; 2; 3; 4; 1; 2; 3; 4; 5]
> [1..4].bind(fun x -> [11..14].bind(fun y -> [(x, y)]));;
val it: (int * int) list =
[(1, 11); (1, 12); (1, 13); (1, 14); (2, 11); (2, 12); (2, 13); (2, 14);
(3, 11); (3, 12); (3, 13); (3, 14); (4, 11); (4, 12); (4, 13); (4, 14)]
リストモナドは内包表記と同じような動作になります。
> let a = seq { for x in [1..4] do for y in [11..14] do (x, y) };;
val a: seq
> for x in a do printfn "%A" x;;
(1, 11)
(1, 12)
(1, 13)
(1, 14)
(2, 11)
(2, 12)
(2, 13)
(2, 14)
(3, 11)
(3, 12)
(3, 13)
(3, 14)
(4, 11)
(4, 12)
(4, 13)
(4, 14)
val it: unit = ()
次は、内包表記の条件節をモナドで実現してみましょう。次の例を見てください。
> [1..10].bind(fun x -> if x % 2 = 0 then [x] else []);;
val it: int list = [2; 4; 6; 8; 10]
> seq { for x in [1..10] do if x % 2 = 0 then x } |> Seq.toList;;
val it: int list = [2; 4; 6; 8; 10]
リストモナドは List.collect でリストを連結します。このとき、空リストは無視されるので、リストに格納された値だけが連結されて返されます。次のように、モナドの途中で if の処理を行うこともできます。
> [1..10].bind(fun x -> (if x % 2 = 0 then [()] else []).bind(fun _ -> [x]));; val it: int list = [2; 4; 6; 8; 10]
bind の左辺値が空リストの場合、リストモナドは空リストを返すことを利用しています。したがって、モナドで連結した処理の途中で空リストが返されると、それ以降の処理は結果が空リストになるのです。空リスト以外の値、たとえば、unit 型を格納したリストを返すと、それ以降の処理が実行されて、条件を満たすデータがリストに格納されて返されます。
この処理は次に示す関数 guard を定義すると簡単です。
リスト : 関数 guard let guard = function true -> [()] | false -> []
guard は引数が真ならば [()] を返し、そうでなければ空リストを返します。それ以降のリストモナドの処理は結果が空リストになり、guard はガードとして機能します。
簡単な実行例を示します。
> let guard = function - true -> [()] - | false -> [];; val guard: _arg1: bool -> unit list > [1..10].bind(fun x -> guard(x % 2 = 0).bind(fun _ -> [x]));; val it: int list = [2; 4; 6; 8; 10]
それでは簡単な例題として、リストモナドを使って順列を生成する関数 permutations n xs を作ってみましょう。permutations はリスト xs から n 個の要素を選択して順列を生成します。プログラムは次のようになります。
リスト : 順列の生成
let permutations n (xs: 'a list) =
let rec iter m ys =
if m = n then [List.rev ys]
else xs.bind(fun x -> guard(not (List.contains x ys)).bind(fun _ -> iter (m + 1) (x::ys)))
iter 0 []
実際の処理は局所関数 iter で行います。引数 m が選んだ要素の個数、ys が選んだ要素を格納するリストです。m が n と等しい場合、順列が一つ完成したので、reverse で ys を反転してからリストに格納して返します。そうでなければ、xs から要素 x を一つ選び、guard で x が ys に含まれていないことを確認して、iter を再帰呼び出しします。
それでは実行してみましょう。
> let permutations n (xs: 'a list) = - let rec iter m ys = - if m = n then [List.rev ys] - else xs.bind(fun x -> guard(not (List.contains x ys)).bind(fun _ -> iter (m + 1) (x::ys))) - iter 0 [];; val permutations: n: int -> xs: 'a list -> 'a list list when 'a: equality > permutations 2 [1..3];; val it: int list list = [[1; 2]; [1; 3]; [2; 1]; [2; 3]; [3; 1]; [3; 2]] > permutations 3 [1..3];; val it: int list list = [[1; 2; 3]; [1; 3; 2]; [2; 1; 3]; [2; 3; 1]; [3; 1; 2]; [3; 2; 1]] > permutations 3 [1..4];; val it: int list list = [[1; 2; 3]; [1; 2; 4]; [1; 3; 2]; [1; 3; 4]; [1; 4; 2]; [1; 4; 3]; [2; 1; 3]; [2; 1; 4]; [2; 3; 1]; [2; 3; 4]; [2; 4; 1]; [2; 4; 3]; [3; 1; 2]; [3; 1; 4]; [3; 2; 1]; [3; 2; 4]; [3; 4; 1]; [3; 4; 2]; [4; 1; 2]; [4; 1; 3]; [4; 2; 1]; [4; 2; 3]; [4; 3; 1]; [4; 3; 2]]
ところで、順列の生成はシーケンスでも行うことができます。
リスト : 順列の生成 (2)
let rec permSeq n (xs: 'a list) =
let rec iter m ys =
seq {
if n = m then List.rev ys
else
for x in xs do
if not(List.contains x ys) then yield! iter (m + 1) (x::ys)
}
iter 0 []
> permSeq 3 [1;2;3] |> Seq.toList;; val it: int list list = [[1; 2; 3]; [1; 3; 2]; [2; 1; 3]; [2; 3; 1]; [3; 1; 2]; [3; 2; 1]] > permSeq 3 [1;2;3;4] |> Seq.toList;; val it: int list list = [[1; 2; 3]; [1; 2; 4]; [1; 3; 2]; [1; 3; 4]; [1; 4; 2]; [1; 4; 3]; [2; 1; 3]; [2; 1; 4]; [2; 3; 1]; [2; 3; 4]; [2; 4; 1]; [2; 4; 3]; [3; 1; 2]; [3; 1; 4]; [3; 2; 1]; [3; 2; 4]; [3; 4; 1]; [3; 4; 2]; [4; 1; 2]; [4; 1; 3]; [4; 2; 1]; [4; 2; 3]; [4; 3; 1]; [4; 3; 2]]
F# でモナドを扱う場合、「コンピュテーション式 (Computation Expressions, 計算式)」を使うと便利です。コンピュータ (F#) ではいろいろな計算が行われます。計算方法は逐次処理だけではなく並行 (並列) 処理がありますし、正格評価や遅延評価、リストモナドのような非決定性計算もあります。このような計算方法を抽象化するための機能がコンピュテーション式です。
F# には以下に示す組み込みのコンピュテーション式が用意されています。
シーケンス と 遅延評価 (lazy 式) は拙作のページで取り上げました。このほかにも、F# では自分でコンピュテーション式を定義することができます。今回はモナドを例題にコンピュテーション式の基本的な使い方について簡単に説明します。
コンピュテーション式はクラスから生成します。クラスを定義するとき、その中で特殊なメソッドを定義すると、そのクラスはコンピュテーション式を生成するクラスとして扱われます。これを「ビルダークラス」といいます。
モナドの場合、基本的な動作は以下に示す 2 つのメソッドを定義するだけです。
型はジェネリックで表記されているので難しくみえますが、Bind の型はモナドそのものです。最初の引数 M<'T> はデータを格納する型 (モナド) をジェネリックで表しています。もう一つの引数の型は 'T -> M<'U> なので、値を同じモナドに格納して返すことが分かります。Return は値をモナドに包んで返します。値を x とすると、option であれば Some x に、Result であれば Ok x に、List であれば [x] となります。
このほかに、メソッド Zero と ReturnFrom を定義しておくと便利です。
ReturnFrom は引数 (モナド) をそのまま返します。Zero は if 式で else が省略されたときに呼び出されます。option, Reuslt, List でいえば失敗を表すデータ None, Error, [] を返します。
コンピュテーション式 cexpr の中では、以下に示す特別な構文を使用することができます。
cexpr { let! ... }
cexpr { do! ... }
cexpr { yield ... }
cexpr { yield! ... }
cexpr { return ... }
cexpr { return! ... }
cexpr { match! ... }
モナドで使用するのは let!, do!, return, return! です。let! と do! は Bind で指定した関数を呼び出します。関数を bind func expr とすると、let! と do! はおおむね次のように動作します。
1. cexpr {
let! x = expr
...
}
=> expr |> bind (fun x -> ...)
2. cexpr {
do! expr
...
}
=> expr |> bind (fun _ -> ...)
let! と do! は式 expr を評価します。その結果はモナドになります。let! はそこから値を取り出して変数にセットします。do! は取り出した値を捨て去ります。そして、それ以降に記述されている式 ... を順番に実行します。つまり、それ以降で let! や do! を記述すれば、各処理を連結していくことができるわけです。
値を返すときは return または return! を使います。return はメソッド Return で指定した処理を、return! はメソッド ReturnFrom で指定した処理を行います。つまり、return は引数をモナドに包んで返し、return! は引数をそのまま返します。
それでは実際に、コンピュテーション式を使って option, Result, List のモナドを作ってみましょう。
リスト : コンピュテーション式によるモナドの実装 (compexpr.fsx) // option type OptionMonadBuilder() = member this.Bind(m, f) = Option.bind f m member this.Return(x) = Some x let optionMonad = OptionMonadBuilder() // Result type ResultMonadBuilder() = member this.Bind(m, f) = Result.bind f m member this.Return(x) = Ok x let resultMonad = ResultMonadBuilder() // List type ListMonadBuilder() = member this.Bind(m, f) = List.collect f m member this.Return(x) = [x] member this.ReturnFrom(x) = x member this.Zero() = [] let listMonad = ListMonadBuilder() let guard = function true -> [()] | false -> []
> #load "compexpr.fsx";;
[読み込み中 /home/mhiroi/fsharp/compexpr.fsx]
namespace FSI_0002
type OptionMonadBuilder =
new: unit -> OptionMonadBuilder
member Bind: m: 'b option * f: ('b -> 'c option) -> 'c option
member Return: x: 'a -> 'a option
val optionMonad: OptionMonadBuilder
type ResultMonadBuilder =
new: unit -> ResultMonadBuilder
member Bind: m: Result<'c,'d> * f: ('c -> Result<'e,'d>) -> Result<'e,'d>
member Return: x: 'a -> Result<'a,'b>
val resultMonad: ResultMonadBuilder
type ListMonadBuilder =
new: unit -> ListMonadBuilder
member Bind: m: 'd list * f: ('d -> 'e list) -> 'e list
member Return: x: 'c -> 'c list
member ReturnFrom: x: 'b -> 'b
member Zero: unit -> 'a list
val listMonad: ListMonadBuilder
val guard: _arg1: bool -> unit list
Bind はモジュールに用意されている関数 Option.bind, Result.bind, List.collect を使えば簡単です。あとは、ビルダークラスを評価して、その結果を変数にセットします。変数名がコンピュテーション式の名前になります。あとは 名前 { ... } でコンピュテーション式を使用することができます。
それでは実行してみましょう。
> open Compexpr;;
> let add x y =
- optionMonad {
- let! a = x
- let! b = y
- return (a + b)
- };;
val add: x: int option -> y: int option -> int option
> add (Some 10) (Some 20);;
val it: int option = Some 30
> add (Some 10) None;;
val it: int option = None
> add None (Some 20);;
val it: int option = None
> let resultAdd x y =
- resultMonad {
- let! a = x
- let! b = y
- return (a + b)
- };;
val resultAdd: x: Result<int,'a> -> y: Result<int,'a> -> Result<int,'a>
> resultAdd ((Ok 10):Result<int,string>) ((Ok 20):Result<int,string>);;
val it: Result<int,string> = Ok 30
> resultAdd ((Ok 10):Result<int,string>) ((Error "oops"):Result<int,string>);;
val it: Result<int,string> = Error "oops"
> resultAdd ((Error "oops"):Result<int,string>) ((Ok 20):Result<int,string>);;
val it: Result<int,string> = Error "oops"
関数 add と resultAdd は、引数に option, Result を受け取り、その値を足し算します。どちらも let! で引数から値を取り出し、加算した値を return で返します。引数が None や Error であれば、None や Error を返します。モナドとして正常に動作していますね。
> listMonad {
- let! x = [1..4]
- let! y = [11..14]
- return (x, y)
- };;
val it: (int * int) list =
[(1, 11); (1, 12); (1, 13); (1, 14); (2, 11); (2, 12); (2, 13); (2, 14);
(3, 11); (3, 12); (3, 13); (3, 14); (4, 11); (4, 12); (4, 13); (4, 14)]
> listMonad {
- let! x = [1..4]
- let! y = [11..14]
- do! guard(x + y > 15)
- return (x, y)
- };;
val it: (int * int) list =
[(2, 14); (3, 13); (3, 14); (4, 12); (4, 13); (4, 14)]
> listMonad {
- let! x = [1..4]
- let! y = [11..14]
- if x + y > 15 then return (x, y)
- };;
val it: (int * int) list =
[(2, 14); (3, 13); (3, 14); (4, 12); (4, 13); (4, 14)]
リストモナドの場合、コンピュテーション式でも内包表記のように使うことができます。do! を使ってガード (関数 guard) を呼び出すこともできます。今回は Zero() を定義してあるので、同様なことを if で行うこともできます。
もちろん、リストモナドで順列を生成することも簡単です。
リスト : 順列の生成
let permMonad n (xs: 'a list) =
let rec iter m ys =
listMonad {
if m = n then return (List.rev ys)
else
let! x = xs
do! guard(not(List.contains x ys))
return! (iter (m + 1) (x::ys))
}
iter 0 []
> permMonad 3 [1..3];; val it: int list list = [[1; 2; 3]; [1; 3; 2]; [2; 1; 3]; [2; 3; 1]; [3; 1; 2]; [3; 2; 1]] > permMonad 3 [1..4];; val it: int list list = [[1; 2; 3]; [1; 2; 4]; [1; 3; 2]; [1; 3; 4]; [1; 4; 2]; [1; 4; 3]; [2; 1; 3]; [2; 1; 4]; [2; 3; 1]; [2; 3; 4]; [2; 4; 1]; [2; 4; 3]; [3; 1; 2]; [3; 1; 4]; [3; 2; 1]; [3; 2; 4]; [3; 4; 1]; [3; 4; 2]; [4; 1; 2]; [4; 1; 3]; [4; 2; 1]; [4; 2; 3]; [4; 3; 1]; [4; 3; 2]]
局所関数 iter の返り値はモナドなので、return! で値を返すことに注意してください。
最後に簡単な論理パズルを解いてみましょう。
３人の友達が、あるプログラミング競技会で１位、２位、３位になった。この３人は、名前も、好きなスポーツも、国籍も異なる。Michael はバスケットが好きで、アメリカ人よりも上位であった。イスラエル人の Simon はテニスをする者よりも上位であった。クリケットをするものが１位であった。誰がオーストラリア人か？ Richard はどのようなスポーツをするか？
簡単な論理パズルなので、プログラムを作る前に考えてみてください。
最初に必要となる型を定義しましょう。
リスト : 型の定義
type Nation = US | IL | AU
type Sports = Basket | Cricket | Tennis
type Name = Michael | Simon | Richard
type Person = {name: Name; rank: int; nation: Nation; sports: Sports}
このデータをリストモナドで作成します。次のリストを見てください。
リスト : データの生成
let makePerson name =
listMonad {
let! r = [1; 2; 3]
let! n = [US; IL; AU]
let! s = [Basket; Cricket; Tennis]
return {name = name; rank = r; nation = n; sports = s}
}
let! で順位 (1, 2, 3)、国籍 (US, IL, AU)、スポーツ (Basket, Cricket, Tennis) の中から要素を一つ選びます。あとは、レコード Person を生成して return で返すだけです。
次は問題を解くための補助関数を作ります。
リスト : 補助関数の定義 // 国籍を探す let findNation n xs = List.find (fun p -> p.nation = n) xs // スポーツを探す let findSports s xs = List.find (fun p -> p.sports = s) xs // 名前以外で重複した要素があるか let isDuplicate x y = x.rank = y.rank || x.nation = y.nation || x.sports = y.sports // 同じ要素があるか let check a b c = isDuplicate a b || isDuplicate a c || isDuplicate b c
findNation は引数のリスト中から国籍が引数 n と等しい要素を返します。findSports は好きなスポーツが引数 s と等しい要素を返します。isDuplicate は引数 a と b に重複した要素があれば true を返します。要素が全て異なる場合は false を返します。関数 check は isDuplicate を呼び出して、引数 a, b, c に重複した要素があれば true を返します。
論理パズルの解法プログラムは次のようになります。
リスト : 論理パズルの解法
let solver () =
listMonad {
let! m = makePerson(Michael)
let! s = makePerson(Simon)
let! r = makePerson(Richard)
do! guard(not(check m s r))
do! guard(m.sports = Basket)
do! guard(m.nation <> US)
do! guard(s.nation = IL)
do! guard(m.rank < (findNation US [m; s; r]).rank)
do! guard(s.rank < (findSports Tennis [m; s; r]).rank)
do! guard((findSports Cricket [m; s; r]).rank = 1)
return (m, s, r)
}
最初に makePerson でデータを作成し、let! で要素を一つ選んで局所変数 m, s, r にセットします。そして、check で順位、国籍、スポーツで要素が重複していないかチェックします。あとは問題の条件を guard でチェックしていくだけです。
最後に、return で見つけた解をタプルに格納して返します。とても簡単ですね。実行結果は次のようになります。
> solver();;
val it: (Person * Person * Person) list =
[({ name = Michael
rank = 2
nation = AU
sports = Basket }, { name = Simon
rank = 1
nation = IL
sports = Cricket }, { name = Richard
rank = 3
nation = US
sports = Tennis })]
解は 1 通りで、１位が Simon, ２位が Michael, ３位が Richard になります。ちなみに、最後の条件がない場合は 2 通りの解が出力されます。興味のある方は試してみてください。
//
// compexpr.fsx : コンピュテーション式によるモナドの実装
//
// Copyright (C) 2022 Makoto Hiroi
//
// option
type OptionMonadBuilder() =
member this.Bind(m, f) = Option.bind f m
member this.Return(x) = Some x
let optionMonad = OptionMonadBuilder()
// Result
type ResultMonadBuilder() =
member this.Bind(m, f) = Result.bind f m
member this.Return(x) = Ok x
let resultMonad = ResultMonadBuilder()
// List
type ListMonadBuilder() =
member this.Bind(m, f) = List.collect f m
member this.Return(x) = [x]
member this.ReturnFrom(x) = x
member this.Zero() = []
let listMonad = ListMonadBuilder()
// ガード
let guard = function
true -> [()]
| false -> []
// 順列の生成
let permMonad n (xs: 'a list) =
let rec iter m ys =
listMonad {
if m = n then return (List.rev ys)
else
let! x = xs
do! guard(not(List.contains x ys))
return! (iter (m + 1) (x::ys))
}
iter 0 []
// 論理パズル
type Nation = US | IL | AU
type Sports = Basket | Cricket | Tennis
type Name = Michael | Simon | Richard
type Person = {name: Name; rank: int; nation: Nation; sports: Sports}
let makePerson name =
listMonad {
let! r = [1; 2; 3]
let! n = [US; IL; AU]
let! s = [Basket; Cricket; Tennis]
return {name = name; rank = r; nation = n; sports = s}
}
// 国籍を探す
let findNation n xs =
List.find (fun p -> p.nation = n) xs
// スポーツを探す
let findSports s xs =
List.find (fun p -> p.sports = s) xs
// 名前以外で重複した要素があるか
let isDuplicate x y =
x.rank = y.rank || x.nation = y.nation || x.sports = y.sports
// 同じ要素があるか
let check a b c =
isDuplicate a b || isDuplicate a c || isDuplicate b c
let solver () =
listMonad {
let! m = makePerson(Michael)
let! s = makePerson(Simon)
let! r = makePerson(Richard)
do! guard(not(check m s r))
do! guard(m.sports = Basket)
do! guard(m.nation <> US)
do! guard(s.nation = IL)
do! guard(m.rank < (findNation US [m; s; r]).rank)
do! guard(s.rank < (findSports Tennis [m; s; r]).rank)
do! guard((findSports Cricket [m;s;r]).rank = 1)
return (m, s, r)
}