モジュール
「モジュール (module)」はデータ構造とそれを操作する関数を一つにまとめるための仕組みです。近年はモジュールに相当する機能を持つプログラミング言語が多くなりました。もちろん、F# にもモジュールがあります。List や Array などの標準ライブラリはモジュールにまとめられています。
●モジュールの定義
F# の場合、キーワード module を使ってモジュールを定義します。module の使い方は二種類あって、ひとつはソースファイルの先頭で module を宣言することです。これを「トップレベルのモジュール」といいます。
module モジュール名
これでソースファイルに書かれている変数、関数、例外、型などがモジュールに格納されます。モジュールに定義されている変数や関数は モジュール名 + "." + 名前 でアクセスすることができます。
なお、F# はトップレベルのモジュールが宣言されていなくても、ソースファイルをモジュールとして扱います。この場合、モジュール名はファイル名の先頭を英大文字に変えたものになります。たとえば、foo.fs や foo.fsx というファイルを #load した場合、モジュール名は Foo となります。
トップレベル以外のモジュールは次の構文で定義します。
module モジュール名 = begin ... end [軽量構文] module モジュール名 = ...
begin ... end がモジュールの本体です。軽量構文を使うと begin と end を省略することができます。モジュールは入れ子にすることができます。たとえば、モジュール Foo の中でモジュール Bar を定義した場合、Bar の変数や関数は Foo.Bar.名前 でアクセスすることができます。
●スタック
それでは簡単な例として、「スタック (stack)」というデータ構造を考えてみましょう。次の図を見てください。
図 1 : スタックの動作例
上図は、バネがついた容器を表していて、上から品物を出し入れすることができます。初めは空の状態です。ここに品物を乗せると、重さによってバネを圧縮し、品物が容器に格納されます。さらにもう一つ品物を上に乗せると、さらにバネを圧縮し、その品物も容器に格納することができます。バネが限界まで圧縮されると、もう品物は追加できなくなります。取り出す場合は、上にある品物から行います。一つ取り出すと、その分バネが伸びて下にある品物が上に押し出されます。
この容器の動作が、スタックの動作なのです。スタックにデータを追加する操作をプッシュ (PUSH) といい、スタックからデータを取り出す操作をポップ (POP) といいます。品物をデータに見立てれば、データ A をスタックにプッシュし (2)、次にデータ B をプッシュします (3)。データを取り出す場合、あとから入れたデータ B が先にポップされ (4)、その次にデータ A がポップされてスタックが空になります (5)。このように、スタックはあとから入れたデータが先に取り出されるので、後入れ先出し (LIFO : Last-In, First-Out) と呼ばれます。
●スタックの実装
F# の場合、スタックはリストを使って簡単に実現することができます。データを追加するときはリストの先頭に追加し、データを取り出すときはリストの先頭から行うように操作を限定すると、スタックの動作と同じになります。プログラムは次のようになります。
リスト 1 : スタック (stack.fs) module Stack // 例外 exception Empty // スタックの定義 type 'a stack = SNil | SCell of 'a * 'a stack // 空のスタック let create = SNil // データの追加 let push st x = SCell (x, st) // データの取得 let top = function SNil -> raise Empty | SCell (x, _) -> x // データの削除 let pop = function SNil -> raise Empty | SCell (_, xs) -> xs // スタックは空か let is_empty st = st = SNil
最初に type でスタック 'a stack を定義します。リストを使ってもいいのですが、ここではヴァリアントで stack 型を定義しています。データ構造はリストと同じです。空のスタックを返す create は関数ではなく変数として定義します。
スタックの操作関数は簡単です。push はデータを stack の先頭に追加します。pop は stack の先頭要素を取り除きます。データの取得は関数 top で行います。スタックが空の場合、pop と top を適用することができないので、例外 Empty を送出します。関数 is_empty はスタックが空かチェックする述語です。
実際に stack.fs を読み込むと次のように表示されます。
> #load "stack.fs";;
[読み込み中 /home/mhiroi/fsharp/stack.fs]
namespace FSI_0002
exception Empty
type 'a stack =
| SNil
| SCell of 'a * 'a stack
val create: 'a stack
val push: st: 'a stack -> x: 'a -> 'a stack
val top: _arg1: 'a stack -> 'a
val pop: _arg1: 'a stack -> 'a stack
val is_empty: st: 'a stack -> bool when 'a: equality
module Stack が省略されていますが、モジュール内で定義されている要素の型が表示されます。これを「シグネチャ (signature)」といいます。シグネチャはモジュールの仕様を記述したものです。モジュールを定義するとシグネチャが生成されますが、ユーザーがシグネチャを定義して、それをモジュールに設定することもできます。シグネチャはあとで簡単に説明します。
簡単な実行例を示します。
> let a0 = Stack.create;; val a0: 'a Stack.stack > let a1 = Stack.push a0 1;; val a1: int Stack.stack = SCell (1, SNil) > let a2 = Stack.push a1 2;; val a2: int Stack.stack = SCell (2, SCell (1, SNil)) > Stack.top a2;; val it: int = 2 > let a3 = Stack.pop a2;; val a3: int Stack.stack = SCell (1, SNil) > Stack.is_empty a3;; val it: bool = false > let a4 = Stack.pop a3;; val a4: int Stack.stack = SNil > Stack.is_empty a4;; val it: bool = true
正常に動作していますね。関数型言語の場合、変数の値を書き換えることができないので、push や pop の返り値を別の変数に格納する必要があります。このとき、参照型の変数にスタックを格納すれば、値を書き換えることができるので便利なように思います。これはあとで試してみましょう。
●open 宣言
ここで open 宣言を使うと、モジュール名を省略することができます。
open モジュール名
> open Stack;; > let b = create;; val b: 'a stack > let c = push b 10;; val c: int stack = SCell (10, SNil)
open 宣言は同じ名前が既に存在している場合、元の名前を隠蔽してしまいます。ご注意くださいませ。
●名前空間
F# はトップレベルのモジュールのかわりに「名前空間 (namespace)」を使うことができます。
namspace 名前
モジュールと違って、名前空間は変数や関数などの値を直接定義することはできません。値を定義するためのモジュールが必要になります。たとえば、名前空間 Foo の中にモジュール Bar を定義する場合、Bar の中の要素 name は Foo.Bar.name でアクセスすることができます。
簡単な例として、リスト 1 の stack.fs を名前空間を使って書き直すと次のようになります。
リスト 2 : スタック (名前空間を使用)
namespace Mylib
module Stack =
// 例外
exception Empty
// スタックの定義
type 'a stack = SNil | SCell of 'a * 'a stack
// 空のスタック
let create = SNil
// データの追加
let push st x = SCell (x, st)
// データの取得
let top = function
SNil -> raise Empty
| SCell (x, _) -> x
// データの削除
let pop = function
SNil -> raise Empty
| SCell (_, xs) -> xs
// スタックは空か
let is_empty st = st = SNil
> #load "stack.fsx";;
[読み込み中 /home/mhiroi/fsharp/stack.fsx]
namespace FSI_0003.Mylib
exception Empty
type 'a stack =
| SNil
| SCell of 'a * 'a stack
val create: 'a stack
val push: st: 'a stack -> x: 'a -> 'a stack
val top: _arg1: 'a stack -> 'a
val pop: _arg1: 'a stack -> 'a stack
val is_empty: st: 'a stack -> bool when 'a: equality
> open Mylib.Stack;;
> let a = create;;
val a: 'a stack
> let b = push a 123;;
val b: int stack = SCell (123, SNil)
open 宣言で名前空間を省略することもできます。open Mylib.Stack とすれば、名前空間とモジュール名を省略することができます。
名前空間は一つのソースファイルの中で複数定義することができます。
namespace Foo ... 略 ... namespace Bar ... 略 ...
名前空間 Foo の範囲は、最初の namespace から次の namespace までの間です。二番目の Bar は次の namespace まで、またはファイルの終わりまでになります。名前空間を入れ子にする場合は、名前で明示してください。たとえば、Foo の中で Bar を定義するには次のように記述します。
namespace Foo ... 略 ... namespace Foo.Bar ... 略 ...
namespace Foo.Bar と宣言することで、Foo の中に Bar を定義することができます。
●シグネチャの定義
次はシグネチャについて簡単に説明します。F# の場合、シグネチャはファイルで定義します。拡張子は .fsi とします。たとえば、ソースファイル foo.fs のシグネチャは foo.fsi に記述します。foo.fs を「実装ファイル」といい、foo.fsi を「シグネチャファイル」といいます。
シグネチャファイルでも名前空間やモジュールを宣言しますが、その名前は実装ファイルと同じでなければいけません。そして、モジュールの中で要素の型 (仕様) を記述します。以下に主な仕様を示します。
- データ型は type で記述する。
- 例外は exception で記述する。
- 関数、変数は "val 名前 : 型式" で記述する。
F# のシグネチャファイルは実装ファイルの仕様を記述したものですが、もう一つ重要な役割として外部とのインターフェースがあります。たとえば、モジュールの内部だけで使用する変数や関数は、外部から使われることがないように隠した方がよいでしょう。
このような場合、外部に公開する関数や変数だけをシグネチャに記述すればよいのです。シグネチャに記述されていない変数や関数は非公開となり、外部からアクセスすることができなくなります。また、type で定義されているコンストラクタも、シグネチャに記述しなければ隠蔽することができます。
たとえば Stack の場合、次のように type で型が宣言されています。
type 'a stack = SNil | SCell of 'a * 'a stack
この場合、コンストラクタ SNil や SCell が公開されるので、コンストラクタを使ってスタックを生成したり、パターンマッチングでスタックの要素を取り出すことができます。
> let a1 = SCell (1, SNil);; val a1: int stack = SCell (1, SNil) > match a1 with - | SNil -> 0 - | SCell (x, _) -> x;; val it: int = 1
このように、コンストラクタが公開されているとスタックを直接操作することが可能となります。データ構造を隠蔽したい場合、シグネチャで宣言する type の右辺を記述しません。具体的には次のようにシグネチャファイルを定義します。
リスト 3 : データ構造の隠蔽 (stack.fsi) namespace Mylib module Stack = type 'a stack exception Empty val create: 'a stack val push: 'a stack -> 'a -> 'a stack val top: 'a stack -> 'a val pop: 'a stack -> 'a stack val is_empty: 'a stack -> bool when 'a: equality
これでコンストラクタを利用することができなくなります。簡単な実行例を示しましょう。
> #load "stack.fsi" "stack.fs";;
[読み込み中 /home/mhiroi/fsharp/stack.fsi
読み込み中 /home/mhiroi/fsharp/stack.fs]
namespace FSI_0002.Mylib
exception Empty
type 'a stack =
| SNil
| SCell of 'a * 'a stack
val create: 'a stack
val push: 'a stack -> 'a -> 'a stack
val top: 'a stack -> 'a
val pop: 'a stack -> 'a stack
val is_empty: 'a stack -> bool when 'a: equality
> open Mylib.Stack;;
> let a1 = SCell (1, SNil);;
let a1 = SCell (1, SNil);;
---------^^^^^
/home/mhiroi/fsharp/stdin(3,10): error FS0039: 値またはコンストラクター 'SCell' が定義されていません。
シグネチャファイルのロードは実装ファイルをロードする前に行ってください。
シグネチャを使ってデータ構造を隠蔽する方法は OCaml と同じですが、F# にはアクセス制御指定子 (public、internal、private) を使ってアクセスを制御する方法も用意されています。これはモジュールでも使用することができるので、こちらを使ったほうが簡単かもしれません。たとえば、次のように type の右辺で private を指定します。
type 'a stack = private SNil | SCell of 'a * 'a stack
これでコンストラクタ SNil, SCell を非公開にできるので、外部から使用することができなくなります。アクセス制御については「オブジェクト指向」を取り上げるときに詳しく説明する予定です。
●参照型を使ったスタックの実装
ところで、スタックを参照型の変数に格納しておいて、その値を書き換えることでスタックの状態を更新することができます。手続き型言語のプログラミングスタイルになりますが、for ループや while ループと組み合わせて使うときには便利でしょう。次のリストを見てください。
リスト 4 : 参照型のスタック (stack1.fs)
module Stack
// 例外
exception Empty
// スタックの定義
type 'a stack = private SNil | SCell of 'a * 'a stack
// 空のスタック
let create () = ref SNil
// データの追加
let push (st: 'a stack ref) x =
st.Value <- SCell (x, st.Value)
// データの取得
let top (st: 'a stack ref) =
match st.Value with
SNil -> raise Empty
| SCell (x, _) -> x
// データの削除
let pop (st: 'a stack ref) =
match st.Value with
SNil -> raise Empty
| SCell (x, xs) -> st.Value <- xs; x
// スタックは空か
let is_empty (st: 'a stack ref) = st.Value = SNil
create は空のスタックの参照を返す関数として定義します。操作関数はスタックを格納した参照型の変数を受け取ります。この変数を書き換えることで、スタックを操作することができます。関数 pop は仕様を変更して、取り除いたデータを返すことにします。あとは特に難しいところはないでしょう。
それでは簡単な実行例を示します。
> #load "stack1.fs";;
[読み込み中 /home/mhiroi/fsharp/stack1.fs]
namespace FSI_0002
exception Empty
type 'a stack =
private | SNil
| SCell of 'a * 'a stack
val create: unit -> 'a stack ref
val push: st: 'a stack ref -> x: 'a -> unit
val top: st: 'a stack ref -> 'a
val pop: st: 'a stack ref -> 'a
val is_empty: st: 'a stack ref -> bool when 'a: equality
> open Stack;;
> let a : int stack ref = create ();;
val a: int stack ref = { contents = SNil }
> for i = 1 to 10 do push a i done;;
val it: unit = ()
> while not (is_empty a) do printfn "%d" (pop a) done;;
10
9
8
7
6
5
4
3
2
1
val it: unit = ()
正常に動作してますね。
●キュー
もう一つ簡単な例として、「キュー (queue)」という基本的なデータ構造を作ってみましょう。キューは「待ち行列」といわれるデータ構造です。たとえばチケットを買う場合、窓口に長い列ができますが、それと同じだと考えてください。チケットを買うときは、列の途中に割り込むことはできませんね。いちばん後ろに並んで順番を待たなければいけません。列の先頭まで進むと、チケットを購入することができます。
このように、要素を取り出す場合は列の先頭から行い、要素を追加する場合は列の後ろに行うデータ構造がキューなのです。キューは「先入れ先出し (FIFO : first-in, first-out)」とも呼ばれます。
キューにデータを入れることを enqueue といい、キューからデータを取り出すことを dequeue といいます。リストを使ってキューを実装する場合、上図のようにキューの先頭とリストの先頭を対応させます。すると、キューからデータを取り出すには、リストの先頭からデータを取り出すだけですみます。これはとても簡単ですね。
ただし、キューにデータを入れるには、リストの最後尾にデータを追加することになるため、ちょっとした工夫が必要になります。たとえば、データの追加に演算子 @ を使うと、データを追加するたびにリスト（キュー）がコピーされてしまいます。このため、キューに格納されているデータが多くなると時間がかかるようになります。
この場合、対策として次のような方法が考えられます。
(1) 最後尾のセルを参照する変数を用意する。 (2) 循環リスト (circular list) というデータ構造を使う。
OCaml の 参考文献 1 は (1) の方法でキューを実装しています。また、OCaml のモジュール Queue は (2) の方法を使っています。どちらの方法も簡単にキューを実装できますが、参照型変数 (または mutable のレコード) を使う必要があります。
そこで、今回はちょっと変わった方法ですが、連結リストを 2 つ使ってキューを作ってみましょう。なお、この方法は SML/NJ のライブラリを参考にしました。
次の図を見てください。
上図は 2 つのリストでキューを表しています。データを取り出すときは front のリストを、データを追加するときは rear のリストを使います。front と rear で一つのキューを構成し、rear のリストはデータを逆順で格納することになります。ようするに、front が先頭で rear が最後尾になるわけです。上図のキューを一つのリストで表すと [0; 1; 2; 3; 4; 5] になります。
したがって、front が空リストでも rear にデータがあれば、キューは空ではありません。rear のリストを逆順にして front にセットし、rear を空リストにします。これで front からデータを取り出すことができます。キューが空の状態は front と rear が両方とも空リストの場合です。
●キューの実装
それではプログラムを作りましょう。次のリストを見てください。
リスト 5 : キュー (queue.fs) module Queue // 例外 exception Empty // データ型の定義 type 'a queue = private Q of 'a list * 'a list // 空のキューを返す let create = Q ([], []) // データの挿入 let enqueue a = function Q (front, rear) -> Q (front, a::rear) // データの削除 let rec dequeue = function Q ([], []) -> raise Empty | Q ([], rear) -> dequeue (Q (List.rev rear, [])) | Q (x::front, rear) -> Q (front, rear) // 先頭のデータを取得 let rec top = function Q ([], []) -> raise Empty | Q ([], rear) -> top (Q (List.rev rear, [])) | Q (x::_, _) -> x // キューは空か let is_empty q = q = create
キューを表すデータ型は 'a queue としました。型式は 'a list * 'a list で、組の第 1 要素が front で第 2 要素が rear になります。例外 Empty は空のキューからデータを取り出そうとしたときに送出します。キューの生成には変数 create を使います。create の値は空のキュー Q ([], []) です。
関数 enqueue はキューにデータ x を追加します。これは x を rear の先頭に追加するだけです。関数 dequeue はキューからデータを取り除きます。キューが空の場合は例外 Empty を送出します。front が空リストの場合は、キュー Q (List.rev rear, []) を作って dequeue を再帰呼び出しします。front にデータがある場合は先頭要素を取り除くだけです。
関数 top はキューの先頭要素を返します。処理は dequeue とほとんど同じで、front の先頭データ x を返すだけです。関数 is_empty は、キューが空であれば true を、そうでなければ false を返します。
最後に簡単な実行例を示します。
> #load "queue.fs";; [読み込み中 /home/mhiroi/fsharp/queue.fs] namespace FSI_0002 exception Empty type 'a queue = private | Q of 'a list * 'a list val create: 'a queue val enqueue: a: 'a -> _arg1: 'a queue -> 'a queue val dequeue: _arg1: 'a queue -> 'a queue val top: _arg1: 'a queue -> 'a val is_empty: q: 'a queue -> bool when 'a: equality > open Queue;; > let a0 = create;; val a0: 'a queue > is_empty a0;; val it: bool = true > let a1 = enqueue 1 a0;; val a1: int queue = Q ([], [1]) > let a2 = enqueue 2 a1;; val a2: int queue = Q ([], [2; 1]) > is_empty a2;; val it: bool = false > top a2;; val it: int = 1 > let a3 = dequeue a2;; val a3: int queue = Q ([2], []) > top a3;; val it: int = 2 > let a4 = dequeue a3;; val a4: int queue = Q ([], []) > is_empty a4;; val it: bool = true
図 5 : 8 クイーンの解答例