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<'a> : func: ('a -> 'a0 maybe) -> 'a0 maybe member Map<'a> : 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<'a> : func: ('a -> either<'a0,'b>) -> either<'a0,'b> member Map<'a> : 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<'a> with member bind: f: ('a -> 'a0 list) -> 'a0 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: (int * int) 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]]