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.Compexpr
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)
}