書き換え可能なデータ型
ML (SML/NJ, OCaml など) は関数型言語なので、関数の引数や let で定義した局所変数の値を書き換えることはできません。ところが、ML には値を書き換えることができるデータ型が用意されています。OCaml の場合、「配列 (array)」と「参照 (reference)」というデータ型は値を書き換えることができます。また、レコードの場合もフィールド名の前にキーワード mutable を付けると書き換え可能なデータ型になります。
これらのデータ型を使うと、手続き型言語のように「副作用」を伴う操作を行うことができます。関数型言語としては不純な機能なのですが、問題によっては配列や参照を使った方が簡単にプログラムできる場合もあります。
●配列
OCaml の配列はＣ言語の 1 次元配列のことで、型は 'a array で表されます。配列は入れ子にできるので、多次元配列も簡単に実現することができます。なお、OCaml の配列は、リストと同様に要素は同じデータ型でなければいけません。
OCaml の場合、配列は [| a1; a2; ...; an |] で生成します。配列のアクセスは次の式で行います。
参照 : 式.(添字) 更新 : 式.(添字) <- 式
Ｃ言語と同様に、配列の要素は 0 から数えます。簡単な例を示しましょう。
# let a = [|10; 20; 30; 40; 50|];; val a : int array = [|10; 20; 30; 40; 50|] # a.(0);; - : int = 10 # a.(4);; - : int = 50 # a.(0) <- 100;; - : unit = () # a;; - : int array = [|100; 20; 30; 40; 50|] # let aa = [| [|10; 20; 30|]; [|40; 50; 60|] |];; val aa : int array array = [| [|10; 20; 30|]; [|40; 50; 60|] |] # aa.(0).(0);; - : int = 10 # aa.(1).(2);; - : int = 60 # aa.(0).(0) <- 100;; - : unit = () # aa;; - : int array array = [| [|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.make と Array.init で生成することができます。
# Array.make;; - : int -> 'a -> 'a array = <fun> # Array.init;; - : int -> (int -> 'a) -> 'a array = <fun>
Array.make は第 1 引数に配列の大きさを指定し、第 2 引数の値で配列を初期化します。Array.init は第 1 引数に配列の大きさを指定するのは同じですが、第 2 引数には要素の初期値を与える関数を渡します。この関数には配列の添字が引数として渡されます。簡単な例を示しましょう。
# Array.make 5 0;; - : int array = [|0; 0; 0; 0; 0|] # Array.init 5 (fun x -> x);; - : int array = [|0; 1; 2; 3; 4|]
配列の大きさは関数 Array.length で求めることができます。
# let a = Array.make 5 0;; val a : int array = [|0; 0; 0; 0; 0;|] # Array.length a;; - : int = 5
関数 Array.append は 2 つの配列を結合した新しい配列を返します。
# Array.append [|1; 2; 3|] [|4; 5; 6|] - : int array = [|1; 2; 3; 4; 5; 6|]
関数 Array.to_list は配列をリストに、Array.of_list はリストを配列に変換します。
# Array.to_list [|0; 1; 2; 3 ;4|] - : int list = [0; 1; 2; 3; 4] # Array.of_list [0; 1; 2; 3; 4] - : int array = [|0; 1; 2; 3; 4|]
Array には配列用の高階関数も用意されています。
val Array.map : ('a -> 'b) -> 'a array -> 'b array
val Array.iter : ('a -> unit) -> 'a array -> unit
val Array.fold_left : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a
val Array.fold_right : ('a -> 'b -> 'b) -> 'a array -> 'b -> 'b
map, iter, fold_left, fold_right は今までに説明した高階関数の配列バージョンです。このほかにも便利な関数が用意されています。詳細は OCaml のリファレンスをお読みください。
●参照
「参照 (reference)」はデータを間接的に参照する機能です。一般に、変数束縛は変数とデータを直接結び付けます。これに対し、参照は変数とデータを直接結び付けるのではなく、その間にデータを指し示す特別なデータ型を入れます。このデータ型を「参照型」といいます。次の図を見てください。
上図 (A) は通常の変数束縛です。let a = 11 とすると、変数 a は数値 11 に束縛されます。これに対し、図 (B) が参照を図示したものです。変数 b は参照型データに束縛され、参照型データが数値 11 を指し示しています。変数 b は参照型データを経由して数値 11 を参照することができます。
OCaml で参照型データを生成するには 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 に束縛します。
参照先のデータを求めるには演算子 ! を使います。変数 b と c に演算子 ! を適用すると、次のようになります。
# !b;; - : int = 11 # !c;; - : string = "foo"
参照型データは参照するデータを変更することができます。次の図を見てください。
上図 (C) は参照するデータを数値 11 から数値 22 に変更しています。すると、変数 b が参照する値は 22 になります。ようするに、変数 b の値を書き換えることと同じ効果が得られるわけです。値の書き換えは演算子 := で行います。次の例を見てください。
# b := 22;; - : unit = () # !b;; - : int = 22 # c := "bar";; - : unit = () # !c;; - : string = "bar"
b := 22 とすると、変数 b の値は 11 から 22 に書き換えられます。同様に、c := "bar" とすると、変数 c の値は "foo" から "bar" になります。
●書き換え可能なレコード
OCaml のレコードはフィールド名にキーワード mutable を付けると、その値を書き換えることができます。実をいうと、OCaml はレコードを使って 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;;
- : unit = ()
# a;;
val a : foo = {bar = 100; baz = 1.23}
●多相性の制限
書き換え可能なデータ型を使う場合、多相性が制限されることがあります。たとえば、空リスト [ ] の参照を考えてみましょう。実際に ref [ ] で参照を生成すると次のようになります。
# let a = ref [];;
val a = '_a list ref = {contents = []}
# a := [1; 2; 3];;
- : unit = ()
# a;;
- : int list ref = {contents = [1; 2; 3]}
生成されるデータ型は '_a list になります。'_a は型変数ではなく、OCaml が型を推論できずに暫定的に付けた型名で、'a list のような多相的な型ではありません。たとえば、a に [1; 2; 3] をセットすると、データ型は int list ref になり、ここでデータ型が決定されます。このあと、他のデータ型に変更することはできません。もしも、'a list のような多相的な型の参照を許すと、次のような代入操作が可能になります。
let a = ref [] (* 型が 'a list とする *) a := [1; 2; 3] (* int list に書き換える *) a := ["abc"; "def"] (* string list に書き換える *)
変数 a の型が int list から string list に変わってしまいます。つまり、プログラムの実行中に変数の型が変化する可能性があるわけです。OCaml はコンパイル時にデータ型を厳密にチェックするプログラミング言語です。実行中にデータ型が変化するような処理は、OCaml には想定外のことです。参照を使う場合は多相性を制限する必要があるのです。
実際にはもう少し制限が厳しくて、変数に「値」を束縛するときに限り、多相性を許すようになっています。参考 URL 3 によると、これを「値多相」と呼ぶそうです。この場合の「値」とは、変数、定数、関数定義、要素が値の組やレコードなどです。逆に、関数や ref の適用、mutable を含むレコード、if など評価が行われる式は「値」になりません。次の例を見てください。
# let times2 f x = f (f x);;
val times2 : ('a -> 'a) -> 'a -> 'a = <fun>
# times2 (fun x -> x * 2) 10;;
- : int = 40
# let times4 = times2 times2;;
val times4 : ('_a -> '_a) -> '_a -> '_a = <fun>
# times4 (fun x -> x * 2) 10;;
- : int = 160
# times4;;
val times4 : (int -> int) -> int -> int = <fun>
関数 f を 2 回適用する関数 times2 を定義します。times2 は多相型関数になります。次に、times2 を使って関数を 4 回適用する関数 times4 を定義します。ここで部分適用を使って let times4 = times2 times2 と定義します。すると、times4 は多相型関数にはなりません。let の右辺は関数の定義ではなく、部分適用によって生成された関数が与えられるため、多相性が制限されるのです。次のように関数として定義すれば、times4 は多相型関数になります。
# let times4' f x = times2 times2 f x;;
val times4' : ('a -> 'a) -> 'a -> 'a = <fun>
多相性の話は難しいですね。参考 URL 3 には型推論と多相性のことがわかりやすく説明されています。興味のある方は一読されることをおすすめします。
●繰り返し
今まで繰り返しは再帰定義を使ってきましたが、OCaml には簡単な繰り返しを行う while 式と for 式が用意されています。まずは while 式から説明しましょう。
while expr1 do expr2 done
while 式は 式 1 を評価し、その結果が真である限り式 2 を繰り返し評価します。while 式の処理を図に示すと次のようになります。
図を見ればおわかりのように while 式はいたって単純ですが、条件が偽にならないと「無限ループ」に陥ってしまうので注意してください。while 式はユニットを返します。簡単な例を示しましょう。
リスト 3 : 階乗 (while 版)
let fact n =
let i = ref n and v = ref 1 in
while !i > 0 do
v := !v * !i;
i := !i - 1
done;
!v
階乗を求める関数 fact を while 式を使ってプログラムしています。let で変数 i, v を定義し、その値を書き換えながら階乗 n * (n - 1) * ... * 2 * 1 を計算しています。最後に階乗の値 !v を返します。
for 式は次の 2 通りの形式があります。
(1) for 変数 = 式1 to 式2 do 式3 done (2) for 変数 = 式1 downto 式2 do 式3 done
式 1 と式 2 の評価結果は整数 (int) でなければいけません。式 1, 2 の値が m, n とすると、(1) は m, m + 1, m + 2, ..., n の順に変数を束縛して式 3 を繰り返し評価します。(2) は m, m - 1, m - 2, ..., n の順に変数を束縛して式 3 を繰り返し評価します。
簡単な例として、階乗のプログラムを for 式で書き直してみましょう。
リスト 4 : 階乗 (for 版)
let fact n =
let v = ref 1 in
for i = 2 to n do
v := !v * i
done;
!v
while 式を使うよりも簡単になりましたね。while 式や for 式は配列と組み合わせて使うと便利です。
●FizzBuzz 問題
次は FizzBuzz 問題を OCaml で解いてみましょう。FizzBuzz 問題は 1 から 100 までの値を表示するとき、3 の倍数のときは Fizz を、5 の倍数ときは Buzz を表示するというものです。FizzBuzz 問題の詳細については Fizz Buzz - Wikipedia をお読みください。
プログラムは次のようになります。
リスト 5 : FizzBuzz 問題
let change_fizzbuzz n =
if n mod 15 = 0 then "FizzBuzz"
else if n mod 3 = 0 then "Fizz"
else if n mod 5 = 0 then "Buzz"
else string_of_int n
let fizzbuzz () =
for n = 1 to 100 do
print_string (change_fizzbuzz n);
print_string " "
done
# 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 までのリストを生成して、それをマッピングで Fizz Buzz に変換することもできます。プログラムは次のようになります。
リスト 6 : FizzBuzz 問題 (別解) let rec iota n m = if n > m then [] else n :: iota (n + 1) m let fizzbuzz1 () = List.map change_fizzbuzz (iota 1 100)
# fizzbuzz1 ();; - : 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
print_int (comb (n, r));
print_string " "
done;
print_newline ()
done
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 : パスカルの三角形 (リスト版)
(* int list の表示 *)
let print_intlist xs =
List.iter (fun x -> print_int x; print_string " ") xs;
print_newline ()
(* パスカルの三角形*)
let rec pascal_list n a =
let rec pascal_sub = function
_ :: [] -> [1]
| x1 :: x2 :: xs -> (x1 + x2) :: pascal_sub (x2 :: xs)
| _ -> raise (Failure "pascal_sub")
in
print_intlist 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 =
for i = 1 to n do
print_int ary.(i); print_string " "
done;
print_newline ()
(* パスカルの三角形 *)
let pascal_array n =
let ary = Array.make (n + 1) 0 in
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);
done;
print_intarray (i + 1) ary
done
配列はひとつあれば十分です。ただし、配列の値を書き換えていくので、配列の後方から計算していくことに注意してください。前方から計算すると、値がおかしくなります。実行結果は同じなので省略します。
リストと配列を使ってパスカルの三角形を作りましたが、もっとクールな方法があるかもしれません。興味のある方は挑戦してみてください。
●数値積分
最後に数値積分で円周率πを求めてみましょう。区間 [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 次近似で精度を上げる「シンプソン則」という方法があります。
それでは実際に、中点則でπの値を求めてみましょう。πは次の式で求めることができます。
プログラムは次のようになります。
リスト 10 : 数値積分で円周率を求める
let mid_point n =
let w = 1.0 /. (float_of_int n) in
let s = ref 0.0 in
for i = 1 to n do
let x = ((float_of_int i) -. 0.5) *. w in
s := !s +. 4.0 /. (1.0 +. x *. x)
done;
!s *. w
val mid_point : int -> float = <fun>
引数 n が分割数です。最初に小区間の幅を求めて変数 w にセットします。面積は変数 s にセットします。次の while ループで区間 [0, 1] を n 個に分割して面積を求めます。
最初に x 座標を計算します。中間点を求めるため、変数 i を 1 から始めて、x 座標を次の式で求めます。
x = ((float_of_int i) -. 0.5) *. w
たとえば、変数 i が 1 の場合は 0.5 になるので、x は区間 [0 * w, 1 * w] の中間点になります。あとは、4 / (1 + x * x) を計算して s に加算します。最後に s に w を掛け算して全体の面積を求めます。
実行結果を示します。
# mid_point 100;; - : float = 3.14160098692312539 # mid_point 1000;; - : float = 3.14159273692312269 # mid_point 10000;; - : float = 3.14159265442313407
分割数 n を増やすと精度が高くなることがわかります。中点則の場合、分割数を 10 倍すると誤差はほぼ 1/100 になることが知られています。
改訂 2020 年 6 月 28 日