モジュール
「モジュール (module)」はデータ構造とそれを操作する関数を一つにまとめるための仕組みです。最近はモジュールに相当する機能を持つプログラミング言語が多くなりました。もちろん、OCaml にもモジュールがあります。List や Array などの標準ライブラリはモジュールにまとめられています。
●スタック
簡単な例として「スタック (stack)」というデータ構造を考えてみましょう。次の図を見てください。
図 : スタックの動作例
上図は、バネがついた容器を表していて、上から品物を出し入れすることができます。初めは空の状態です。ここに品物を乗せると、重さによってバネを圧縮し、品物が容器に格納されます。さらにもう一つ品物を上に乗せると、さらにバネを圧縮し、その品物も容器に格納することができます。バネが限界まで圧縮されると、もう品物は追加できなくなります。取り出す場合は、上にある品物から行います。一つ取り出すと、その分バネが伸びて下にある品物が上に押し出されます。
この容器の動作が、スタックの動作なのです。スタックにデータを追加する操作をプッシュ (PUSH) といい、スタックからデータを取り出す操作をポップ (POP) といいます。品物をデータに見立てれば、データ A をスタックにプッシュし (2)、次にデータ B をプッシュします (3)。データを取り出す場合、あとから入れたデータ B が先にポップされ (4)、その次にデータ A がポップされてスタックが空になります (5)。このように、スタックはあとから入れたデータが先に取り出されるので、後入れ先出し (LIFO : Last-In, First-Out) と呼ばれます。
なお、OCaml には標準ライブラリにモジュール Stack が用意されています。今回は OCaml の勉強ということで、実際にスタックを作ってみましょう。
●スタックの定義
OCaml の場合、スタックはリストを使って簡単に実現することができます。データを追加するときはリストの先頭に追加し、データを取り出すときはリストの先頭から行うように操作を限定すると、スタックの動作と同じになります。
最初はモジュールを使わずにプログラムを作ります。次のリストを見てください。
リスト 1 : スタック (* 例外 *) 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 はスタックが空かチェックする述語です。
簡単な使用例を示します。
# let a0 = create;; val a0 : 'a stack = SNil # let a1 = push a0 1;; val a1 : int stack = SCell (1, SNil) # let a2 = push a1 2;; val a2 : int stack = SCell (2, SCell (1, SNil)) # top a2;; - : int = 2 # let a3 = pop a2;; val a3 : int stack = SCell (1, SNil) # is_empty a3;; - : bool = false # let a4 = pop a3;; val a4 = int stack = SNil # is_empty a4;; - : bool = true
正常に動作していますね。関数型言語の場合、変数の値を書き換えることができないので、push や pop の返り値を別の変数に格納する必要があります。このとき、参照型の変数にスタックを格納すれば、値を書き換えることができるので便利なように思います。実際、OCaml のモジュール Stack は mutable なレコードにリストを格納しています。これはあとで試してみましょう。
●モジュールの定義
それでは、モジュールを使ってスタックを定義してみましょう。OCaml の場合、キーワード module を使ってモジュールを定義することができますが、もう一つ簡単な方法があります。OCaml はソースファイルをモジュールとして扱うことができす。
たとえば、スタックのプログラムがファイル mystack.ml に格納されているとしましょう。ここで mystack.ml を ocamlc で次のようにバイトコンパイルします。
$ ocamlc -c mystack.ml $ ls mystack* mystack.cmi mystack.cmo mystack.ml
mystack.cmi は mystack.ml のインターフェースを記述したもので、mystack.cmo は mystack.ml をコンパイルしたオブジェクトファイルです。cmo ファイルはディレクティブ #load でロードすることができます。このとき、cmo ファイルはファイル名の先頭を英大文字に変えたモジュールとして扱われます。つまり mystack.cmo をロードすると、そこに定義されている関数や変数は Mystack というモジュールに格納されます。
# #load "mystack.cmo";; # let a = Mystack.create;; val a : 'a Mystack.stack = Mystack.SNil
このように、cmo ファイルをロードすると、そこに定義されている関数や変数は "モジュール名 + ドット ( . ) + 名前" でアクセスすることができます。また、open 宣言を使うと、モジュール名を省略することができます。
# open Mystack;; # let b = create;; val b : 'a Mystack.stack = SNil
open 宣言は同じ名前が既に存在している場合、元の名前を隠蔽してしまいます。ご注意ください。このように、ソースファイルをモジュールとして扱うことができると、複数の関数や変数を簡単にまとめることができるのでとても便利です。
●module による実装
次は module 宣言を使ってモジュールを定義する方法を説明します。module の構文を示します。
module 名前 = struct ... end
struct ... end がモジュールの本体です。この中で変数、関数、例外、データ型などを定義します。モジュール名を Mystack とすると、スタックのプログラムは次のようになります。
リスト 2 : モジュールの定義
module Mystack = struct
(* 例外 *)
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
end
OCaml の場合、モジュール名は英大文字で始めます。リスト 2 はstruct と end の間にスタックのプログラム (リスト 1) をそのまま書いただけです。とても簡単ですね。実際に Stack を定義すると次のように表示されます。
# #use "mystack.ml";;
module Mystack :
sig
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
end
sig ... end を「シグネチャ (signature)」といいます。シグネチャはモジュールの仕様を記述するものですが、OCaml のシグネチャはモジュールの型も表しています。モジュールを定義するとシグネチャが生成されますが、ユーザーがシグネチャを定義して、それをモジュールに設定することもできます。シグネチャは次節で詳しく説明します。
それでは実行してみましょう。
# let a0 = Mystack.create;; val a0 : 'a Mystack.stack = Mystack.SNil # let a1 = Mystack.push a0 1;; val a1 : int Mystack.stack = Mystack.SCell (1, Mystack.SNil) # let a2 = Mystack.push a1 2;; val a2 : int Mystack.stack = Mystack.SCell (2, Mystack.SCell (1, Mystack.SNil)) # Mystack.top a2;; - : int = 2 # let a3 = Mystack.pop a2;; val a3 : int Mystack.stack = Mystack.SCell (1, Mystack.SNil) # Mystack.is_empty a3;; - : bool = false # let a4 = Mystack.pop a3;; val a4 : int Mystack.stack = Mystack.SNil # Mystack.is_empty a4;; - : bool = true
Mystack を open すると、もっと簡単にアクセスできるようになります。
●シグネチャとデータ抽象
次はシグネチャについて説明します。シグネチャは module type 宣言を使って定義します。
module type 名前 = sig ... end
sig ... end がシグネチャの本体です。この間にモジュールの仕様を書きます。主な仕様は次のように記述します。
- データ型は type で記述する。
- 例外は exception で記述する。
- 関数、変数は "val 名前 : 型式" で記述する。
シグネチャはモジュールの仕様を記述したものですが、もう一つ重要な役割として外部とのインターフェースがあります。たとえば、モジュールの内部だけで使用する変数や関数は、外部から使われることがないように隠した方がよいでしょう。このような場合、外部に公開する関数や変数だけをシグネチャに記述すればよいのです。シグネチャに記述されていない変数や関数は非公開となり、外部からアクセスすることができなくなります。
また、type で定義されているコンストラクタも、シグネチャに記述しなければ隠蔽することができます。たとえば Stack の場合、次のように type でデータ型が宣言されています。
type 'a stack = SNil | SCell of 'a * 'a stack
この場合、コンストラクタ SNil や SCell が公開されるので、パターンマッチングを使って要素を取り出すことができます。
# a1;; - : int Mystack.stack = Mystack.SCell (1, Mystack.SNil) # let Mystack.SCell(x, _) = a1;; ... 警告 ... val x : int = 1
警告が出ますが無視してください。このように、スタックを直接操作してデータを取り出すことができます。データ構造を隠蔽したい場合、シグネチャで宣言する type の右辺を記述しません。具体的には次のようにシグネチャを定義します。
リスト 3 : データ構造の隠蔽 module type MYSTACK = sig type 'a stack exception Empty val create : 'a stack val push : 'a stack -> 'a -> 'a stack val pop : 'a stack -> 'a stack val top : 'a stack -> 'a val is_empty : 'a stack -> bool end module Stack1: MYSTACK = Mystack
シグネチャの名前はモジュールと同様に英大文字から始めます。ここでは MYSTACK としました。モジュールにシグネチャを指定する場合、モジュール名の後ろにコロン ( : ) を付けて、その後ろにシグネチャを指定します。
OCaml の場合、変数の型を指定するときは "変数名 : 型式" で行います。シグネチャはモジュールの型を表すので、"モジュール名 : シグネチャ" でシグネチャを指定することができます。
この他にも、シグネチャは名前を付けずに指定することもできます。簡単な例を示します。
module Foo : sig ... end = struct ... end module Foo = (struct ... end : sig ... end)
struct の後ろにシグネチャを定義する場合はカッコで囲む必要があります。コロン ( : ) の後ろにシグネチャを指定するところは、どちらの方法でも同じです。
これでコンストラクタを利用することができなくなります。簡単な例を示しましょう。
# let a0 = Stack1.create;; val a0 : 'a Stack1.stack = <abstr>
<abstr> はデータ構造が隠蔽されていることを表しています。この状態でコンストラクタ SCell や SNil を使うとエラーになります。
このように、データ構造の詳細を隠蔽し、操作関数を使ってデータ構造にアクセスすることを「データ抽象 (data abstraction)」とか「カプセル化 (encapsulation)」といいます。わざわざ操作関数を用意するのは面倒なように思われますが、そのことによりプログラムも読みやすくなり、修正にも強いプログラムを作ることができます。
たとえば、スタックの実装をリスト構造から配列に変更することを考えてみましょう。この場合、type の定義はリスト構造から配列に変更されます。もしも、コンストラクタ SCell や SNil を使って直接スタックを操作しているプログラムがあるならば、その箇所を探して修正する必要があります。操作関数だけを使っていて、操作関数の仕様が変わらなければ、スタックを使うプログラムを修正する必要はありません。モジュール Stack を変更するだけで済むわけです。
●mli ファイルの定義
ソースファイルをモジュールとして扱う場合、拡張子が mli のファイルを定義することで、シグネチャと同様にデータ構造を隠蔽することができます。スタックの場合、次のように定義します。
リスト 4 : mystack.mli の内容 type 'a stack exception Empty val create : 'a stack val push : 'a stack -> 'a -> 'a stack val pop : 'a stack -> 'a stack val top : 'a stack -> 'a val is_empty : 'a stack -> bool
mli ファイルの書き方はシグネチャと同じです。このファイルから ocmalc で cmi ファイルを作成します。それから、stack.ml をコンパイルします。
$ ocamlc mystack.mli $ ocamlc -c mystack.ml
これで mystack.mli の仕様を満たしたモジュール Mystack を生成することができます。なお、ocamlc はソースファイルをコンパイルせずに型情報を出力する -i オプションがあります。シグネチャを定義するときは、このオプションを使うと便利です。
●参照型を使ったスタックの実装
ところで、スタックを参照型の変数に格納しておいて、その値を書き換えることでスタックの状態を更新することができます。手続き型言語のプログラミングスタイルになりますが、for ループや while ループと組み合わせて使うときには便利でしょう。次のリストを見てください。
リスト 5 : 参照型のスタック (mystack1.ml)
(* シグネチャ *)
module type MYSTACK = sig
exception Empty
type 'a stack
val create : unit -> 'a stack ref
val push : 'a stack ref -> 'a -> unit
val top : 'a stack ref -> 'a
val pop : 'a stack ref -> 'a
val is_empty : 'a stack ref -> bool
end
(* モジュール *)
module Mystack: MYSTACK = struct
(* 例外 *)
exception Empty
(* スタックの定義 *)
type 'a stack = SNil | SCell of 'a * 'a stack
(* 空のスタック *)
let create () = ref SNil
(* データの追加 *)
let push st x = st := SCell (x, !st)
(* データの取得 *)
let top st =
match !st with
SNil -> raise Empty
| SCell (x, _) -> x
(* データの削除 *)
let pop st =
match !st with
SNil -> raise Empty
| SCell (x, xs) -> st := xs; x
(* スタックは空か *)
let is_empty st = !st = SNil
end
create は空のスタックの参照を返す関数として定義します。操作関数はスタックを格納した参照型の変数を受け取ります。この変数を書き換えることで、スタックを操作することができます。関数 pop は仕様を変更して、取り除いたデータを返すことにします。あとは特に難しいところはないでしょう。
それでは簡単な実行例を示します。
# #use "mystack1.ml";;
module type MYSTACK =
sig
exception Empty
type 'a stack
val create : unit -> 'a stack ref
val push : 'a stack ref -> 'a -> unit
val top : 'a stack ref -> 'a
val pop : 'a stack ref -> 'a
val is_empty : 'a stack ref -> bool
end
module Mystack : MYSTACK
# open Mystack;;
# let a = create ();;
val a : '_a Mystack.stack ref = {contents = <abstr>}
# for i = 1 to 10 do push a i done;;
- : unit = ()
# while not (is_empty a) do print_int (pop a); print_string " " done;;
10 9 8 7 6 5 4 3 2 1 - : unit = ()
正常に動作してますね。
●キュー
もう一つ簡単な例として、「キュー (queue)」という基本的なデータ構造を作ってみましょう。OCaml には標準ライブラリにモジュール Queue がありますが、私達でも簡単にプログラムすることができます。
キューは「待ち行列」といわれるデータ構造です。たとえばチケットを買う場合、窓口に長い列ができますが、それと同じだと考えてください。チケットを買うときは、列の途中に割り込むことはできませんね。いちばん後ろに並んで順番を待たなければいけません。列の先頭まで進むと、チケットを購入することができます。
このように、要素を取り出す場合は列の先頭から行い、要素を追加する場合は列の後ろに行うデータ構造がキューなのです。キューは「先入れ先出し (FIFO : first-in, first-out)」とも呼ばれます。
キューにデータを入れることを enqueue といい、キューからデータを取り出すことを dequeue といいます。リストを使ってキューを実装する場合、上図のようにキューの先頭とリストの先頭を対応させます。すると、キューからデータを取り出すには、リストの先頭からデータを取り出すだけですみます。これはとても簡単ですね。
ただし、キューにデータを入れるには、リストの最後尾にデータを追加することになるため、ちょっとした工夫が必要になります。たとえば、データの追加に演算子 @ を使うと、データを追加するたびにリスト（キュー）がコピーされてしまいます。このため、キューに格納されているデータが多くなると時間がかかるようになります。
この場合、対策として次のような方法が考えられます。
(1) 最後尾のセルを参照する変数を用意する。 (2) 循環リスト (circular list) というデータ構造を使う。
参考文献 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 が両方とも空リストの場合です。
●キューの実装
それではプログラムを作りましょう。次のリストを見てください。
リスト 6 : キュー (myqueue.ml)
module Myqueue:
sig
exception Empty
type 'a queue
val create : 'a queue
val enqueue : 'a -> 'a queue -> 'a queue
val dequeue : 'a queue -> 'a queue
val top : 'a queue -> 'a
val is_empty : 'a queue -> bool
end
= struct
(* 例外 *)
exception Empty
(* データ型の定義 *)
type 'a queue = 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
end
キューを表すデータ型は '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 を返します。
それでは簡単な実行例を示します。
# #use "myqueue.ml";;
module Myqueue :
sig
exception Empty
type 'a queue
val create : 'a queue
val enqueue : 'a -> 'a queue -> 'a queue
val dequeue : 'a queue -> 'a queue
val top : 'a queue -> 'a
val is_empty : 'a queue -> bool
end
# open Myqueue;;
# let a0 = create;;
val a0 : 'a Myqueue.queue = <abstr>
# is_empty a0;;
- : bool = true
# let a1 = enqueue 1 a0;;
val a1 : int Myqueue.queue = <abstr>
# let a2 = enqueue 2 a1;;
val a2 : int Myqueue.queue = <abstr>
# is_empty a2;;
- : bool = false
# top a2;;
- : int = 1
# let a3 = dequeue a2;;
val a3 : int Myqueue.queue = <abstr>
# top a3;;
- : int = 2
# let a4 = dequeue a3;;
val a4 : int Myqueue.queue = <abstr>
# is_empty a4;;
- : bool = true
きちんと動作していますね。
●問題
次の関数を定義してください。
- 自然数 n を素因数分解する関数 factorization n
- 返り値はリスト [(p, q); ...] で、(p, q) は \(p^q\) を表します
- 自然数 n の約数の個数を求める関数 divisor_num
- 自然数 n の約数の合計値を求める関数 divisor_sum
- 自然数 n の約数をリストに格納して返す関数 divisor
val factorization : int -> (int * int) list = <fun> val divisor_num : int -> int = <fun> val divisor_sum : int -> int = <fun> val divisor : int -> int list = <fun>
●解答１
リスト : 素因数分解
let factorization n =
let rec factor_sub n m c =
if n mod m <> 0 then (c, n)
else factor_sub (n / m) m (c + 1)
in
let rec iter i n a =
if n = 1 then List.rev a
else if n < i * i then List.rev ((n, 1)::a)
else
let (c, m) = factor_sub n i 0 in
if c > 0 then iter (i + 2) m ((i, c)::a)
else iter (i + 2) n a
in
let (c, m) = factor_sub n 2 0 in
if c > 0 then iter 3 m [(2, c)]
else iter 3 n []
# factorization 12345678;; - : (int * int) list = [(2, 1); (3, 2); (47, 1); (14593, 1)] # factorization 123456789;; - : (int * int) list = [(3, 2); (3607, 1); (3803, 1)] # factorization 1234567890;; - : (int * int) list = [(2, 1); (3, 2); (5, 1); (3607, 1); (3803, 1)] # factorization 1111111111;; - : (int * int) list = [(11, 1); (41, 1); (271, 1); (9091, 1)]
素因数分解は素数 2, 3, 5, ... で順番に割り算していけばいいのですが、いちいち素数を求めるのは大変なので、2 と 3 以上の奇数列で割り算していきます。局所関数 factor_sub は n を m で割り算します。このとき、m で割り切れる回数を求めます。factor_sub は m で割った回数と商をタプルに格納して返します。
次に、factor_sub を呼び出して n を 2 で割り算します。それから、局所関数 iter で奇数列を生成します。変数 i は 3 で初期化します。a は結果を格納するリストです。n が 1 になる、または \(\sqrt n \lt i\) になったら繰り返しを終了します。そうでなければ、factor_sub を呼び出して n を i で割り算します。奇数列には素数ではないものがありますが、その前に小さな素数で素因数分解されているので、n がその値で割り切れることはありません。
●解答２
リスト : 約数の個数 let divisor_num n = List.fold_left (fun a (_, n) -> a * (n + 1)) 1 (factorization n)
# divisor_num 12345678;; - : int = 24 # divisor_num 123456789;; - : int = 12 # divisor_num 1234567890;; - : int = 48 # divisor_num 1111111111;; - : int = 16
n の素因数分解ができると、約数の個数を求めるのは簡単です。\(n = p^a \times q^b \times r^c\) とすると、約数の個数は \((a + 1) \times (b + 1) \times (c + 1)\) になります。たとえば、12 は \(2^2 \times 3^1\) になるので、約数の個数は 3 * 2 = 6 になります。実際、12 の約数は 1, 2, 3, 4, 6, 12 の 6 個です。
●解答３
リスト : 約数の合計値
(* 累乗 *)
let rec pow x y =
if y = 0 then 1
else
let z = pow x (y / 2) in
let zz = z * z in
if y mod 2 = 0 then zz else x * zz
let divisor_sum n =
let rec iter p n a =
if n = 0 then a + 1
else iter p (n - 1) (a + pow p n)
in
List.fold_left (fun a (p, n) -> a * (iter p n 0))
1
(factorization n)
# divisor_sum 12345678;; - : int = 27319968 # divisor_sum 123456789;; - : int = 178422816 # divisor_sum 1234567890;; - : int = 3211610688 # divisor_sum 1111111111;; - : int = 1246404096
n の素因数分解ができると、約数の合計値を求めるのは簡単です。n の素因数分解が \(p^a\) だった場合、その約数の合計値は次の式で求めることができます。
たとえば、8 の素因数分解は \(2^3\) になり、素数の合計値は 8 + 4 + 2 + 1 = 15 になります。
\(p^a\) の約数の合計値を \(\sigma(p, a)\) で表すことにします。\(n = p^a \times q^b \times r^c\) の場合、n の約数の合計値は \(\sigma(p, a) \times \sigma(q, b) \times \sigma(r, c)\) になります。たとえば、12 は \(2^2 \times 3\) に素因数分解できますが、その合計値は (4 + 2 + 1) * (3 + 1) = 28 となります。12 の約数は 1, 2, 3, 4, 6, 12 なので、その合計値は確かに 28 になります。
●解答４
リスト : 約数をすべて求める
let divisor n =
let rec divisor_sub p n a =
if n = 0 then 1::a
else divisor_sub p (n - 1) ((pow p n)::a)
in
let rec list_product p q a =
match p with
[] -> a
| x::xs -> list_product xs q ((List.map (fun y -> y * x) q) @ a)
in
match factorization n with
[] -> []
| [(p, n)] -> divisor_sub p n []
| (p, n)::xs -> List.sort
compare
(List.fold_left
(fun a (p, n) -> list_product (divisor_sub p n []) a [])
(divisor_sub p n [])
xs)
# divisor 123456789;; - : int list = [1; 3; 9; 3607; 3803; 10821; 11409; 32463; 34227; 13717421; 41152263; 123456789] # divisor 1234567890;; - : int list = [1; 2; 3; 5; 6; 9; 10; 15; 18; 30; 45; 90; 3607; 3803; 7214; 7606; 10821; 11409; 18035; 19015; 21642; 22818; 32463; 34227; 36070; 38030; 54105; 57045; 64926; 68454; 108210; 114090; 162315; 171135; 324630; 342270; 13717421; 27434842; 41152263; 68587105; 82304526; 123456789; 137174210; 205761315; 246913578; 411522630; 617283945; 1234567890] # divisor 1111111111;; - : int list = [1; 11; 41; 271; 451; 2981; 9091; 11111; 100001; 122221; 372731; 2463661; 4100041; 27100271; 101010101; 1111111111]
p が素数の場合、\(p^a\) の約数は次のように簡単に求めることができます。
n の素因数分解が \(p^a \times q^b\) だったとすると、その約数は次のようになります。
たとえば、12 の約数は 24 = (1, 2, 4) と 3 = (1, 3) から、(1, 2, 4) * 1 と (1, 2, 4) * 3 のすべての要素 (1, 2, 4, 3, 6, 12) になります。
局所関数 divisor_sub は pn の約数をリストに格納して返します。局所関数 list_product は 2 つのリスト p, q の要素を掛け合わせたものをリストに格納して返します。あとは fold_left で素因数分解した結果を順番に取り出し、(p . n) を divisor_sub でリストに変換して list_product で累積変数 a のリストと掛け合わせていくだけです。