書き換え可能な型
ML (SML/NJ, OCaml など) は関数型言語なので、関数の引数や let で定義した局所変数の値を書き換えることはできません。ところが、ML には値を書き換えることができる型が用意されています。F# の場合、「配列 (array)」と「参照 (reference)」であれば値を書き換えることができます。また、let の変数名やレコードのフィールド名の前にキーワード mutable を付けると、更新可能な変数やフィールドになります。
mutable な型を使うと、手続き型言語のように「副作用」を伴う操作を行うことができます。関数型言語としては不純な機能なのですが、問題によっては配列や参照を使った方が簡単にプログラムできる場合もあります。
●配列
F# の配列はＣ言語の 1 次元配列のことで、型は 'a[] で表されます。配列は入れ子にできるので、多次元配列も簡単に実現することができます。なお、F# の配列は、リストと同様に要素は同じデータ型でなければいけません。
F# の場合、配列は [| a1; a2; ...; an |] で生成します。[| ... |] の中は軽量構文を使うことができます。インデントを揃えることで、セミコロンを省略することができます。また、リストと同じように [|n .. m|] とすれば、n から m までの数値を格納した配列を生成することができます。[|n .. a .. m|] とすれば、増分値 a を指定することもできます。
配列のアクセスは次の式で行います。
参照 : 式.[添字] 更新 : 式.[添字] <- 式
Ｃ言語と同様に、配列の要素は 0 から数えます。簡単な例を示しましょう。
> let a = [|10; 20; 30; 40; 50|];; val a: int[] = [|10; 20; 30; 40; 50|] > a.[0];; val it: int = 10 > a.[4];; val it: int = 50 > a.[0] <- 100;; val it: unit = () > a;; val it: int[] = [|100; 20; 30; 40; 50|] > let aa = [| [|10; 20; 30|]; [|40; 50; 60|] |];; val aa: int[][] = [|[|10; 20; 30|]; [|40; 50; 60|]|] > aa.[0].[0];; val it: int = 10 > aa.[1].[2];; val it: int = 60 > aa.[0].[0] <- 100;; val it: unit = () > aa;; val it: int[][] = [|[|100; 20; 30|]; [|40; 50; 60|]|]
配列 a の大きさは 5 なので、添字の範囲は 0 から 4 になります。範囲外の添字を指定するとエラーになります。a.[0] はＣ言語の a[0] と同じで、a.[0] <- 100 は a[0] = 100 と同じです。値を書き換えたときの返り値は unit になります。
配列の中に配列を入れると 2 次元配列になります。この場合、要素のアクセスは aa.[添字1].[添字2] になります。たとえば、aa.[0].[0] は最初の aa.[0] で 0 番目の要素を指定します。これは配列 [|10; 20; 30|] ですね。次の .[0] でその 0 番目の要素を指定するので、値は 10 になります。値を書き換える場合も同じです。
●配列の操作関数
ここで、標準ライブラリ Array に用意されている関数をいくつか紹介しましょう。配列は関数 Array.create と Array.init で生成することができます。
> Array.create;; val it: (int -> 'a -> 'a[]) > Array.init;; val it: (int -> (int -> 'a) -> 'a[])
Array.create は第 1 引数に配列の大きさを指定し、第 2 引数の値で配列を初期化します。Array.init は第 1 引数に配列の大きさを指定するのは同じですが、第 2 引数には要素の初期値を与える関数を渡します。この関数には配列の添字が引数として渡されます。
簡単な例を示しましょう。
> Array.create 5 0;; val it: int[] = [|0; 0; 0; 0; 0|] > Array.init 5 (fun x -> x);; val it: int[] = [|0; 1; 2; 3; 4|]
配列の大きさは関数 Array.length で求めることができます。
> let a = Array.create 5 0;; val a: int[] = [|0; 0; 0; 0; 0|] > Array.length a;; val it: int = 5
関数 Array.append は 2 つの配列を結合した新しい配列を返します。
> Array.append [|1; 2; 3|] [|4; 5; 6|];; val it: int[] = [|1; 2; 3; 4; 5; 6|]
関数 Array.toList は配列をリストに、Array.ofList はリストを配列に変換します。
> Array.toList [|0; 1; 2; 3 ;4|];; val it: int list = [0; 1; 2; 3; 4] > Array.ofList [0; 1; 2; 3 ;4];; val it: int[] = [|0; 1; 2; 3; 4|]
Array には配列用の高階関数も用意されています。
> Array.map;;
val it: (('a -> 'b) -> 'a[] -> 'b[])
> Array.iter;;
val it: (('a -> unit) -> 'a[] -> unit)
> Array.fold;;
val it: (('a -> 'b -> 'a) -> 'a -> 'b[] -> 'a)
> Array.foldBack;;
val it: (('a -> 'b -> 'b) -> 'a[] -> 'b -> 'b)
map, iter, fold, foldBack は今までに説明した高階関数の配列バージョンです。このほかにも便利な関数が用意されています。詳細は F# のリファレンス Array Module をお読みください。
●参照
「参照 (reference)」はデータを間接的に参照する機能です。一般に、変数束縛は変数とデータを直接結び付けます。これに対し、参照は変数とデータを直接結び付けるのではなく、その間にデータを指し示す特別な値を入れます。これを「参照型」といいます。次の図を見てください。
上図 (A) は通常の変数束縛です。let a = 11 とすると、変数 a は数値 11 に束縛されます。これに対し、図 (B) が参照を図示したものです。変数 b は参照型データに束縛され、参照型データが数値 11 を指し示しています。変数 b は参照型データを経由して数値 11 を参照することができます。
F# で参照型データを生成するには ref を使います。次の例を見てください。
> let b = ref 11;;
val b: int ref = { contents = 11 }
> let c = ref "foo";;
val c: string ref = { contents = "foo" }
ref 11 は数値 11 を指し示す参照型データを生成し、それを変数 b に束縛します。この場合、データの型は int ref になります。ref "foo" は文字列 "foo" を指し示す string ref を生成し、それを変数 c に束縛します。
参照先のデータを求めるにはプロパティ Value を使います。変数 b と c の値を求めると、次のようになります。
> b.Value;; val it: int = 11 > c.Value;; val it: string = "foo
参照型データは参照するデータを変更することができます。次の図を見てください。
上図 (C) は参照するデータを数値 11 から数値 22 に変更しています。すると、変数 b が参照する値は 22 になります。ようするに、変数 b の値を書き換えることと同じ効果が得られるわけです。値の書き換えは 演算子 <- でプロパティ Value に新しい値を代入します。次の例を見てください。
> b.Value <- 22;; val it: unit = () > b.Value;; val it: int = 22 > c.Value <- "bar";; val it: unit = () > c.Value;; val it: string = "bar"
b.Value <- 22 とすると、変数 b の値は 11 から 22 に書き換えられます。同様に、c.Value <- "bar" とすると、変数 c の値は "foo" から "bar" になります。
●書き換え可能なレコードと変数
F# のレコードはフィールド名にキーワード mutable を付けると、その値を書き換えることができます。実をいうと、F# はレコードを使って ref を実現しています。
type 'a ref = {mutable contents : 'a}
値の書き換えは次のように行います。
式0.フィールド名 <- 式1
簡単な例を示しましょう。
> type foo = {mutable bar : int; baz : float};;
type foo =
{
mutable bar: int
baz: float
}
> let a = {bar = 10; baz = 1.23};;
val a: foo = { bar = 10
baz = 1.23 }
> a.bar <- 100;;
val it: unit = ()
> a;;
val it: foo = { bar = 100
baz = 1.23 }
同様に、F# では let で定義する局所変数に mutable を付けると、更新可能な変数になります。値の更新は演算子 <- を使います。
> let mutable x = 1;; val mutable x: int = 1 > x;; val it: int = 1 > x <- 10;; val it: unit = () > x;; val it: int = 10 > x <- x + 1;; val it: unit = () > x;; val it: int = 11
●多相性の制限
書き換え可能な型を使う場合、多相性が制限されることがあります。たとえば、空リスト [ ] の参照を考えてみましょう。実際に ref [ ] で参照を生成すると次のようになります。
> let a = ref [];;
let a = ref [];;
----^
/home/mhiroi/fsharp/stdin(69,5): error FS0030: 値の制限。
値 'a' は次のジェネリック型を持つと推論されました。
val a: '_a list ref
単純なデータ用語として 'a' を定義するか、明示的な引数を使用して関数にするか、
ジェネリックにする意図がない場合は型の注釈を追加してください。
F# が推論した型は '_a list になります。'_a は型変数ではなく、F# が型を推論できずに暫定的に付けた型名で、'a list のような多相的な型ではありません。もしも、'a list のような多相的な型の参照を許すと、次のような代入操作が可能になります。
let a = ref [] // 型が 'a list とする a.Value <- [1; 2; 3] // int list に書き換える a.Value <- ["abc"; "def"] // string list に書き換える
変数 a の型が int list から string list に変わってしまいます。つまり、プログラムの実行中に変数の型が変化する可能性があるわけです。F# はコンパイル時にデータ型を厳密にチェックするプログラミング言語です。実行中にデータ型が変化するような処理は、F# には想定外のことです。参照を使う場合は多相性を制限する必要があるのです。
実際にはもう少し制限が厳しくて、変数に「値」を束縛するときに限り、多相性を許すようになっています。OCaml の 参考 URL 3 によると、これを「値多相」と呼ぶそうです。この場合の「値」とは、変数、定数、関数定義、要素が値の組やレコードなどです。逆に、関数や ref の適用、mutable を含むレコード、if など評価が行われる式は「値」になりません。次の例を見てください。
> let times2 f x = f (f x);;
val times2: f: ('a -> 'a) -> x: 'a -> 'a
> times2 (fun x -> x * 2) 10;;
val it: int = 40
> let times4 = times2 times2;;
let times4 = times2 times2;;
----^^^^^^
/home/mhiroi/fsharp/stdin(76,5): error FS0030: 値の制限。
値 'times4' は次のジェネリック型を持つと推論されました。
val times4: (('_a -> '_a) -> '_a -> '_a)
明示的に引数を 'times4' にするか、ジェネリックにする意図がない場合は型の注釈を追加してください。
関数 f を 2 回適用する関数 times2 を定義します。times2 は多相型関数になります。
次に、times2 を使って関数を 4 回適用する関数 times4 を定義します。ここで部分適用を使って let times4 = times2 times2 とすると、times4 は多相型関数にはなりません。let の右辺は関数の定義ではなく、部分適用によって生成された関数が与えられるため、多相性が制限されるのです。次のように関数として定義すれば、times4 は多相型関数になります。
> let times4' f x = times2 times2 f x;;
val times4': f: ('a -> 'a) -> x: 'a -> 'a
> times4' (fun x -> x * 2) 10;;
val it: int = 160
多相性の話は難しいですね。OCaml の 参考 URL 3 には型推論と多相性のことがわかりやすく説明されています。興味のある方は一読されることをおすすめします。
●繰り返し
今まで繰り返しは再帰定義を使ってきましたが、OCaml には簡単な繰り返しを行う while 式と for 式が用意されています。まずは while 式から説明しましょう。
while expr1 do expr2; expr3; ... done [軽量構文] while expr1 do expr2 expr3 ...
while 式は expr1 を評価し、その結果が真である限り expr2; expr3; ... を繰り返し評価します。軽量構文を使うとセミコロン ( ; ) と done を省略することができます。while 式の処理を図に示すと次のようになります。
図を見ればおわかりのように while 式はいたって単純ですが、条件が偽にならないと「無限ループ」に陥ってしまうので注意してください。while 式はユニットを返します。簡単な例を示しましょう。
リスト 3 : 階乗 (while 版)
let fact n =
let mutable i = n
let mutable v = 1
while i > 0 do
v <- v * i
i <- i - 1
v
階乗を求める関数 fact を while 式を使ってプログラムしています。let で mutable な変数 i, v を定義し、その値を書き換えながら階乗 n * (n - 1) * ... * 2 * 1 を計算しています。最後に階乗の値 v を返します。
for 式は次の 3 通りの形式があります。
(1) for 変数 = expr1 to expr2 do expr3; ... done
[軽量構文]
for 変数 = expr1 to expr2 do
expr3
...
(2) for 変数 = expr1 downto expr2 do expr3; ... done
[軽量構文]
for 変数 = expr1 downto expr2 do
expr3
...
(3) for pattern in collection do expr1; ... done
[軽量構文]
for pattern in collection do
expr1
...
(1) と (2) の場合、expr1 と expr2 の評価結果は整数 (int) でなければいけません。expr1, expr2 の値が m, n とすると、(1) は m, m + 1, m + 2, ..., n の順に変数を束縛して expr3 以降の式を繰り返し評価します。(2) は m, m - 1, m - 2, ..., n の順に変数を束縛して expr3 以降の式を繰り返し評価します。
(3) は Java や C# などでお馴染みの構文です。collection は複数のデータを格納したコレクション (コンテナ) で、そこから要素を一つずつ取り出して pattern と照合し、expr1 以降の式を繰り返し評価します。
簡単な例を示しましょう。
> for i = 1 to 10 do printfn "%d" i done;; 1 2 3 4 5 6 7 8 9 10 val it: unit = () > for i = 10 downto 1 do printfn "%d" i done;; 10 9 8 7 6 5 4 3 2 1 val it: unit = () > for i in [1..10] do printfn "%d" i done;; 1 2 3 4 5 6 7 8 9 10 val it: unit = ()
もう一つ簡単な例として、階乗のプログラムを for 式で書き直してみましょう。
リスト 4 : 階乗 (for 版)
let fact n =
let mutable v = 1
for i = 2 to n do
v <- v * i
v
while 式を使うよりも簡単になりましたね。while 式や for 式は配列と組み合わせて使うと便利です。
●FizzBuzz 問題
次は FizzBuzz 問題を F# で解いてみましょう。FizzBuzz 問題は 1 から 100 までの値を表示するとき、3 の倍数のときは Fizz を、5 の倍数ときは Buzz を表示するというものです。FizzBuzz 問題の詳細については Fizz Buzz - Wikipedia をお読みください。
プログラムは次のようになります。
リスト 5 : FizzBuzz 問題
let change_fizzbuzz n =
if n % 15 = 0 then "FizzBuzz"
else if n % 3 = 0 then "Fizz"
else if n % 5 = 0 then "Buzz"
else string n
let fizzbuzz () =
for n = 1 to 100 do
printf "%s " (change_fizzbuzz n)
> fizzbuzz ();; 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 FizzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 76 77 Fizz 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 98 Fizz Buzz - : unit = ()
変数 n を 1 に初期化し、for 文の中で 1 ずつ増やしていきます。この中で関数 change_fizzbuzz を呼び出して数値を文字列に変換します。最初の if 文で、n が 15 の倍数 (3 の倍数でかつ 5 の倍数) かチェックします。そうでなければ、次の else if で n が 3 の倍数かチェックし、次の else if で n が 5 の倍数かチェックします。どの条件も該当しない場合は最後の else 節で n を文字列に変換します。
なお、関数型言語らしく 1 から 100 までのリストを生成して、それをマッピングで FizzBuzz に変換することもできます。プログラムは次のようになります。
リスト 6 : FizzBuzz 問題 (別解) let fizzbuzz1 () = List.map change_fizzbuzz [1 .. 100]
> fizzbuzz1();; val it: string list = ["1"; "2"; "Fizz"; "4"; "Buzz"; "Fizz"; "7"; "8"; "Fizz"; "Buzz"; "11"; "Fizz"; "13"; "14"; "FizzBuzz"; "16"; "17"; "Fizz"; "19"; "Buzz"; "Fizz"; "22"; "23"; "Fizz"; "Buzz"; "26"; "Fizz"; "28"; "29"; "FizzBuzz"; "31"; "32"; "Fizz"; "34"; "Buzz"; "Fizz"; "37"; "38"; "Fizz"; "Buzz"; "41"; "Fizz"; "43"; "44"; "FizzBuzz"; "46"; "47"; "Fizz"; "49"; "Buzz"; "Fizz"; "52"; "53"; "Fizz"; "Buzz"; "56"; "Fizz"; "58"; "59"; "FizzBuzz"; "61"; "62"; "Fizz"; "64"; "Buzz"; "Fizz"; "67"; "68"; "Fizz"; "Buzz"; "71"; "Fizz"; "73"; "74"; "FizzBuzz"; "76"; "77"; "Fizz"; "79"; "Buzz"; "Fizz"; "82"; "83"; "Fizz"; "Buzz"; "86"; "Fizz"; "88"; "89"; "FizzBuzz"; "91"; "92"; "Fizz"; "94"; "Buzz"; "Fizz"; "97"; "98"; "Fizz"; "Buzz"]
●パスカルの三角形
もう一つ簡単な例題として、再帰定義 の「組み合わせの数」で作成した関数 comb を使って「パスカルの三角形」を作ってみましょう。次の図を見てください。
図 : パスカルの三角形
パスカルの三角形は、左側の図のように両側がすべて 1 で、内側の数はその左上と右上の和になっています。これは \((a + b)^n\) を展開したときの各項の係数を表しています。そして、その値は右側の図のように組み合わせの数 \({}_n \mathrm{C}_r\) に対応しています。
きれいな三角形にはなりませんが、パスカルの三角形を表示するプログラムを示します。
リスト 7 : パスカルの三角形を表示
let pascal x =
for n = 0 to x - 1 do
for r = 0 to n do
printf "%d " (comb (n, r));
printfn ""
for 式で「二重ループ」を構成しています。最初のループで n の値を 0 から x - 1 まで増やし、次のループで r の値を 0 から n まで増やしています。あとは comb (n, r) を計算して値を表示するだけです。
それでは実行結果を示します。
> pascal 10;; 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 val it: unit = ()
ところで、関数 comb を使わなくてもパスカルの三角形を出力するプログラムを作ることができます。リストと配列のどちらを使っても簡単です。
パスカルの三角形は、両側がすべて 1 で内側の数はその左上と右上の和になっています。したがって、n 段の三角形を作る場合、一段前の値を記憶しておいて隣同士の要素を足し算すればいいわけです。一段前の値をリストに格納すると、プログラムは次のようになります。
リスト 8 : パスカルの三角形 (リスト版)
// list の表示
let print_list xs = printfn "%A" xs
// パスカルの三角形
let rec pascal_list n a =
let rec pascal_sub = function
_ :: [] -> [1]
| x1 :: x2 :: xs -> (x1 + x2) :: pascal_sub (x2 :: xs)
| _ -> failwith "pascal_sub"
print_list a
if n > 1 then pascal_list (n - 1) (pascal_sub (0 :: a))
局所関数 pascal_sub は、リストの隣同士の要素を足した値をリストに格納して返します。この処理は再帰呼び出しを使えば簡単です。リストの先頭要素と次の要素を足し算し、その値を再帰呼び出しの返り値にコンス演算子で追加すればいいわけです。
リストの要素がひとつになると、最初の節とマッチングするので再帰呼び出しが停止します。ここでリスト [1] を返します。pascal_sub を呼び出すときはリストの先頭に 0 を追加します。これで、リストの先頭と最後尾を 1 にすることができます。あとは、pascal_list で pascal_sub を呼び出すだけです。実行結果は同じなので省略します。
次は、配列を使ってプログラムを作ります。n 段の三角形を作る場合、大きさが n + 1 の配列を用意します。たとえば、6 段の三角形を作ってみましょう。次の図を見てください。
最初に配列の内容を 0 に初期化し、1 番目に 1 をセットします。これが 1 段目になります。あとは図のように、隣の要素を足し算するだけです。プログラムは次のようになります。
リスト 9 : パスカルの三角形 (配列版)
// int array の表示
let print_intarray n (ary: int[]) =
for i = 1 to n do
printf "%d " ary.[i]
printfn ""
// パスカルの三角形
let pascal_array n =
let ary = Array.create (n + 1) 0
ary.[1] <- 1
print_intarray 1 ary
for i = 1 to n - 1 do
for j = i + 1 downto 1 do
ary.[j] <- ary.[j] + ary.[j - 1]
print_intarray (i + 1) ary
配列はひとつあれば十分です。ただし、配列の値を書き換えていくので、配列の後方から計算していくことに注意してください。前方から計算すると、値がおかしくなります。実行結果は同じなので省略します。
リストと配列を使ってパスカルの三角形を作りましたが、もっとクールな方法があるかもしれません。興味のある方は挑戦してみてください。
●数値積分
最後に数値積分で円周率πを求めてみましょう。区間 [a, b] の定積分 \(\int_{a}^{b} f(x) \, dx\) を数値的に求めるには、区間を細分して小区間の面積を求めて足し上げます。小区間の面積を求める一番簡単な方法は長方形で近似することです。この場合、3 つの方法が考えられます。
- (b - a) * f(a)
- (b - a) * f(b)
- (b - a) * f((a + b) / 2)
1 は左端の値 f(a) を、2 は右端の値 f(b) を、3 は中間点の値 f((a + b) / 2) を使って長方形の面積を計算します。この中で 3 番目の方法が一番精度が高く、これを「中点則」といいます。このほかに、台形で近似する「台形則」や、2 次近似で精度を上げる「シンプソン則」という方法があります。
それでは実際に、中点則で \(\pi\) の値を求めてみましょう。\(\pi\) は次の式で求めることができます。
プログラムは次のようになります。
リスト 10 : 数値積分で円周率を求める
let mid_point n =
let w = 1.0 / (float n)
let mutable s = 0.0
for i = 1 to n do
let x = ((float i) - 0.5) * w
s <- s + 4.0 / (1.0 + x * x)
s * w
val mid_point : int -> float = <fun>
引数 n が分割数です。最初に小区間の幅を求めて変数 w にセットします。面積は変数 s にセットします。次の for ループで区間 [0, 1] を n 個に分割して面積を求めます。
最初に x 座標を計算します。中間点を求めるため、変数 i を 1 から始めて、x 座標を次の式で求めます。
x = ((float i) - 0.5) * w
たとえば、変数 i が 1 の場合は 0.5 になるので、x は区間 [0 * w, 1 * w] の中間点になります。あとは、4 / (1 + x * x) を計算して s に加算します。最後に s に w を掛け算して全体の面積を求めます。
実行結果を示します。
> mid_point 100;; val it: float = 3.141600987 > mid_point 1000;; val it: float = 3.141592737 > mid_point 10000;; val it: float = 3.141592654 > mid_point 100 |> printfn "%.15f";; 3.141600986923125 val it: unit = () > mid_point 1000 |> printfn "%.15f";; 3.141592736923123 val it: unit = () > mid_point 10000 |> printfn "%.15f";; 3.141592654423134 val it: unit = () > mid_point 100000 |> printfn "%.15f";; 3.141592653598162 val it: unit = ()
printfn の引数 "%.15f" は、浮動小数点数を小数点以下 15 桁で表示する書式です。分割数 n を増やすと精度が高くなることがわかります。中点則の場合、分割数を 10 倍すると誤差はほぼ 1/100 になることが知られています。