Functional Programming

データ型の定義

近代的なプログラミング言語は、ユーザーが既存のデータ型を組み合わせて、新しいデータ型を定義する機能を備えています。OCaml の場合、組を使って新しい型を表すことができますが、このほかに「ヴァリアント (variant)」と「レコード (record)」というデータ構造を定義する方法があります。

●ヴァリアントの定義

最初にヴァリアントから説明します。ヴァリアントはＣ言語の共用体とよく似ているデータ構造です。OCaml の場合、新しいデータ型を定義するときは type 宣言を使います。ヴァリアントを定義する構文を次に示します。

type (型変数, ... 型変数) 型の名前 =
  データ構成子A of 型式A
| データ構成子B of 型式B
   ...
| データ構成子N of 型式N

「型式 (type expression)」とはデータ型を表す式のことで、基本的なデータ型である int, float, string, bool などのほかに、関数型や組を表す積型、list と組み合わせてできる int list や string list などがあります。データ構成子 (コンストラクタ) とは型式のデータを表す名前です。OCaml の場合、コンストラクタ名は英大文字から始めます。コンストラクタはデータを生成するときやパターンマッチングのときに使用します。

なお、異なるバリアント型で同名のコンストラクタを定義すると、後から定義したコンストラクタが有効になり、前に定義したコンストラクタは隠蔽されます。たとえば、ヴァリアント foo でコンストラクタ Baz を定義します。その後でバリアント bar でコンストラクタ Baz を定義すると、Baz で生成したデータ型は bar になります。Baz で foo のデータ型は生成できません。ご注意ください。

●ヴァリアントの生成

もっとも簡単なヴァリアントは、Ｃ言語などの列挙型 (enum) のように使う方法です。次の例を見てください。

# type fruit = Apple | Orange | Grape;;
type fruit = Apple | Orange | Grape
# Apple;;
- : fruit = Apple
# Grape;;
- : fruit = Grape
# Orange;;
- : fruit = Orange

fruit というデータ型は Apple, Orange, Grape から構成されます。このあと、Apple, Orange, Grape を OCaml のプログラムで使うことができます。次のように fruit を組やリストに入れることもできます。

# let a = [Apple; Orange; Grape];;
val a : fruit list = [Apple; Orange; Grape]
# let b = (Apple, Orange);;
val b : fruit * fruit = (Apple, Orange)

また、ヴァリアントはＣ言語の共用体とよく似た働きをします。たとえば、number というデータ型を定義してみましょう。次の例を見てください。

# type number = Int of int | Float of float;;
type number = Int of int | Float of float
# Int 10;;
- : number = Int 10
# Float 1.1;;
- : number = Float 1.1
# [Int 1; Float 1.5; Int 2; Float 2.5];;
- : number list = [Int 1; Float 1.5; Int 2; Float 2.5]

number は数を表すデータ型で、データは整数 (int) または実数 (float) です。Int of int によりコンストラクタ Int の型は int と定義され、Float of float でコンストラクタ Float の型は float と定義されます。

データ型 number の生成はコンストラクタを使います。Int 10 または Float 1.1 で number 型のデータが生成されます。Int (10) や Float (1.1) のようにカッコで囲んでもかまいません。最後の例のように、number 型のデータをリストに格納することができます。このように新しいデータ型 number を定義することで、整数と実数をいっしょにリストに格納することができます。

●パターンマッチング

コンストラクタは「パターン」として使うことができます。たとえば、number list の整数と実数の合計値を別々に求める関数 number_sum を作ってみましょう。次のリストを見てください。

リスト 1 : 整数と実数の合計値を別々に求める

let number_sum xs =
  let rec sum xs a b = 
    match xs with
      [] -> (a, b)
    | Int y :: ys -> sum xs (a + y) b
    | Float y :: ys -> sum xs a (b +. y)
  in
    sum xs 0 0.0

number_sum は整数と実数の合計を求め、組 (int * float) にして返します。実際の処理は局所関数 sum で行います。sum の第 2, 3 引数を累積変数として使い、第 2 引数に整数の合計値、第 3 引数に実数の合計値を求めます。Int y :: ys と Float y :: ys がパターンです。リストの先頭の要素が Int の場合、2 番目の定義とマッチングして、y の値は整数になります。要素が Float の場合は 3 番目の定義とマッチングして、y の値は実数になります。

それでは実行例を示します。

val number_sum = number list -> int * float = <fun>

# number_sum [Int 10; Int 11; Real 2.5; Int 12; Real 3.1; Real 4.2];;
- : int * float = (33, 9.8)

●option 型

型変数を使うと 'a list のような多相的なデータ型を作ることができます。簡単な例として、OCaml に定義されている option 型をみてみましょう。option の定義を示します。

type 'a option = None | Some of 'a

型変数は type と名前の間に指定します。複数の型変数を使う場合は ('a, 'b, ... 'n) のように、型変数をカッコで囲んでカンマで区切ります。option はデータの有無を表す型です。データが無い場合は None を、データが有る場合は Some を使います。Some の型式は 'a なので、どのデータ型でも option に格納することができます。次の例を見てください。

# None;;
- : 'a option = None
# Some 10;;
- : int option = Some 10
# Some "foo";;
- : string option = Some "foo"

None だけではデータ型を定めることができないので、型は 'a option と表示されます。Some 10 の場合、与えられたデータ型が int なので int option になります。同様に、Some "foo" の型は string option になります。

たとえば、リストからデータを探索する処理を考えてみましょう。「リストの探索」で作成した関数 member は、データが見つかれば残りのリストを、見つからなければ空リストを返すように作りました。見つけたデータをそのまま返さないのは、データが見つからない場合の返り値である空リストとデータ型を一致させるためです。

OCaml はデータ型を厳密にチェックするプログラミング言語なので、異なるデータ型を返すことはできません。このような場合、役に立つのが option です。見つけたデータをそのまま返さずに、option に格納して返せばいいわけです。

簡単な例として、リストの中から述語を満たす要素を探す関数 find_if を作ってみましょう。OCaml には List.find という同じ機能を持つ関数が用意されていますが、私達でも簡単に作ることができます。ちなみに、関数名は Common Lisp から拝借しました。

リスト 2 : リストの探索

let rec find_if f = function
  [] -> None
| x :: xs -> if f x then Some x else find_if f xs

最初の節で、データが見つからない場合は None を返します。次の節で、述語 f x が真を返せば Some x を返します。そうでなければ、find_if を再帰呼び出しして次の要素を調べます。

それでは、簡単な実行例を示します。

val find_if : ('a -> bool) -> 'a list -> 'a option

# find_if (fun x -> x >= 10) [1; 2; 11; 12; 3; 4];;
- : int option = Some 11
# find_if (fun x -> x >= 10) [1; 2; 3; 4; 5; 6];;
- : int option = None

データが見つからない場合は None を返しますが、リストの要素が int なので None のデータ型も int option になります。なお、option の値はパターンマッチングを使って取り出すことができます。

●再帰的なデータ型

ヴァリアントは再帰的なデータ構造も定義することができます。たとえば、連結リスト (linkedlist) は次のように定義することができます。

type 'a linkedlist = Nil | Cell of 'a * 'a linkedlist

Nil が連結リストの終端を表し、Cell がコンスセルを表します。積型 'a * 'a linkedlist で、最初の要素が格納するデータになり、2 番目の要素が次の Cell を格納するデータになります。これで Ocaml のリストと同等の多相的なデータ型になります。次の例を見てください。

# type 'a linkedlist = Nil | Cell of 'a * 'a linkedlist;;
type 'a linkedlist = Nil | Cell of 'a * 'a linkedlist
# let a = Cell (1, Nil);;
val a : int linkedlist = Cell (1, Nil)
# let b = Cell (2, a);;
val b : int linkedlist = Cell (2, Cell (1, Nil))
# let c = Cell (10, Cell (11, Cell (12, Nil)));;
val c : int linkedlist = Cell (10, Cell (11, Cell (12, Nil)))

このように、Cell を使って linkedlist を組み立てることができます。ようするに、コンストラクタ Cell が list のコンス演算子と同じ働きをしているわけです。実際、Ocaml の list は次のように定義されています。

type 'a list = [] | :: of 'a * 'a list

これで多相的なリスト構造を実現できるのですから、OCaml の型システムは柔軟で強力な機能だと思います。

●連想リスト

それでは簡単な例題として、「連想リスト (association list : a-list)」を作ってみましょう。前回簡単に説明しましたが、連想リストは組 (key, data) を要素としたリストです。OCaml には連想リストを操作する関数が List モジュールに用意されています。今回は OCaml の学習ということで、あえて｢連想リスト」を表すデータ型とその操作関数を作成してみましょう。

最初にヴァリアントでデータ型を定義します。

リスト 3 : 連想リストの定義

type ('a, 'b) alist = ANil | ACell of 'a * 'b * ('a, 'b) alist

名前は alist にしたので、型は ('a, 'b) alist になります。'a がキーで 'b がデータに対応する型になります。ANil が空の連想リストを表します。ACell の内部では 'a と 'b を組 ('a * 'b) にする必要はないので、ACell の型式は 'a * 'b * ('a, 'b) list としました。

次に連想リストを生成する関数を作りましょう。関数名は Common Lisp から拝借しました。次のリストを見てください。

リスト 4 : 連想リストの生成

let acons x y ls = ACell (x, y, ls)

let rec pairlis xs ys =
  match (xs, ys) with
    (([], _) | (_, [])) -> ANil
  | (x1::xs1, y1::ys1) -> ACell (x1, y1, (pairlis xs1 ys1))

関数 acons はキー x とデータ y と連想リスト ls を受け取り、ls の先頭に x と y を追加します。関数 pairlis は 2 つのリストを受け取り、第 1 引数のリストの要素がキー、第 2 引数のリストの要素がデータとなる連想リストを生成します。引数のリストの長さが違う場合は短い方に合わせます。

最初の節がどちらかのリストが空になった場合です。複数のパターンを | でつなぐパターンを「or パターン」といいます。パターンのどれかがマッチングに成功すれば、その節を選択して評価します。最後の節で ACell を生成して xs の要素 x1 と ys の要素 y1 を格納します。

次はデータを探索する関数を作ります。関数 assoc は指定したキーと等しいデータを探します。関数 assoc_if は述語が真となるキーを探します。どちらの関数も、データを option に格納して返します。見つからない場合は None を返します。

リスト 5 : 連想リストの探索

let rec assoc key = function
  ANil -> None
| ACell (x, y, rest) -> if x = key then Some y else assoc key rest

let rec assoc_if f = function
  ANil -> None
| ACell (x, y, rest) -> if f x then Some y else assoc_if f rest

どちらの関数もパターンマッチングで ACell 内のデータを取り出しています。x がキーで、y がデータ、rest が次の ACell です。連想リストが空 (ANil) の場合は None を返します。assoc は引数 x とキー a を比較して、等しければ Some b を返します。assoc_if は f x の評価結果が真であれば Some b を返します。

それでは、簡単な実行例を示します。

val acons : 'a -> 'b -> ('a, 'b) alist -> ('a, 'b) alist = <fun>
val pairlis : 'a list -> 'b list -> ('a, 'b) alist = <fun>
val assoc : 'a -> ('a, 'b) alist -> 'b option = <fun>
val assoc_if : ('a -> bool) -> ('a, 'b) alist -> 'b option = <fun>

# let a = acons 1 10 ANil;;
val a : (int, int) alist = ACell (1, 10, ANil)
# let b = acons 2 12 a;;
val b : (int, int) alist = ACell (2, 12, ACell (1, 10, ANil))
# let c = pairlis [1; 2; 3; 4; 5] [11; 12; 13; 14; 15];;
val c : (int,int) alist = ... 省略 ...

# assoc 4 c;;
- : int option = Some 14
# assoc_if (fun x -> x mod 2 = 0) c;;
^ : int option = Some 12

正常に動作していますね。

●レコードの定義

次は「レコード (record)」について説明します。レコードはＣ言語の構造体と同じようなデータ構造です。レコードは type 宣言で次のように定義します。

type (型引数, ...) 型名 = {
  フィールド名1 : 型1; フィールド名2 : 型2; ... ; フィールド名n : 型n
}

type 宣言の後ろに型名を指定し、その後ろに中カッコ { } で本体を定義します。要素は "フィールド名 : 型" の形式で指定してカンマで区切ります。なお、異なるレコード型で同じフィールド名を使用することはできません。フィールド名が重複している場合、あとから定義したレコードが有効になり、その前に定義したレコードは使うことができなくなります。ご注意ください。

●レコードの生成

レコードは次の形式で生成します。

{ フィールド名1 = 式1; フィールド名2 = 式2; ... ; フィールド名n = 式n }

式の評価結果がフィールドの値になります。簡単な例を示しましょう。

# type foo = {bar : int; baz : float};;
type foo = { bar : int; baz : float; }
# let a = {bar = 10; baz = 1.23};;
val a : foo = {bar = 10; baz = 1.23}
# a.bar;;
- : int = 10
# a.baz;;
- : float = 1.23

フィールドの値はパターンマッチングで取り出すこともできますが、"レコード + ドット ( . ) + フィールド名" の形式で取り出すこともできます。

OCaml はフィールドの値を変更した新しいレコードを生成することができます。次の例を見てください。

# let b = {a with baz = 123.4};;
val b : foo = {bar = 10; baz = 123.4}
# a;;
val a : foo = {bar = 10; baz = 1.23}

{式0 with フィールド名 = 式; ... } という形式で、式0 で得られるレコードのフィールドの値を、指定した式の評価値に変更した新しいレコードを生成します。なお、元のレコードの値を書き換えることはありません。

●レコードのパターンマッチング

もちろん、レコードでもパターンマッチングを使うことができます。次の例を見てください。

# let {bar = x; baz = y} = a;;
val x : int = 10
val y : float = 1.23
# let {baz = z} = a;;
val z = 1.23

"フィールド = パターン" とするとフィールドの値とパターンを照合します。{bar = x; baz = y} は変数 x とフィールド bar の値、変数 y とフィールド bar の値がマッチングして、x = 10, y = 1.23 になります。また、レコードのパターンマッチングは、必要なフィールドだけを指定することができます。フィールド名からレコードの型が分かるので、すべてのフィールドを指定する必要はありません。

●多相的なレコード

レコードは型変数を使って多相的なデータ構造を定義することができます。たとえば、キーとデータの組を表すレコードは次のように定義することができます。

# type ('a, 'b) pair = {key : 'a; data : 'b};;
type ('a, 'b) pair = { key : 'a; data : 'b; }

キー (key) の型を 'a で、データ (data) の型を 'b で表しています。

簡単な例題として、pair を使って連想リストを作ってみましょう。レコードはヴァリアントと組み合わせることができます。次のリストを見てください。

リスト 6 : 連想リストの定義

type ('a, 'b) alist = ANil | ACell of ('a, 'b) pair * ('a, 'b) alist

ACell の型は ('a, 'b) pair * ('a, 'b) alist になります。

連想リストを生成する関数 acons と pairlis は次のようになります。

リスト 7 : 連想リストの生成

let acons x y xs = ACell ({key = x; data = y}, xs)

let rec pairlis xs ys =
  match (xs, ys) with
    (([], _) | (_, [])) -> ANil
  | (x1::xs1, y1::ys1) -> ACell ({key = x1; data = y1}, (pairlis xs1 ys1))

どちらの関数もキーとデータをレコードに格納するだけです。

データを探索する関数 assoc と assoc_if は次のようになります。

リスト 8 : 連想リストの探索

let rec assoc key = function
  ANil -> None
| ACell ({key = x; data = y}, rest) -> if x = key then Some y else assoc key rest

let rec assoc_if f = function
  ANil -> None
| ACell ({key = x; data = y}, rest) -> if f x then Some y else assoc_if f rest

どちらの関数もパターンマッチングでレコードから値を取り出します。レコードはフィールドに名前が付いているので、組と違ってデータの順番を気にする必要はなく、わかりやすいプログラムになると思います。

それでは、簡単な実行例を示します。

val acons : 'a -> 'b -> ('a, 'b) alist -> ('a, 'b) alist = <fun>
val pairlis : 'a list -> 'b list -> ('a, 'b) alist = <fun>
val assoc : 'a -> ('a, 'b) alist -> 'b option = <fun>
val assoc_if : ('a -> bool) -> ('a, 'b) alist -> 'b option = <fun>

# let a = acons 1 10 ANil;;
val a : (int, int) alist = ACell ({key = 1; data = 10}, ANil)
# let b = acons 2 12 a;;
val b : (int, int) alist =
ACell ({key = 2; data = 12}, ACell ({key = 1; key = 10}, ANil))
# let c = pairlis [1; 2; 3; 4; 5] [11; 12; 13; 14; 15];;
val c : (int,int) alist = ... 省略 ...

# assoc 4 c;;
- : int option = Some 14
# assoc_if (fun x -> x mod 2 = 0) c;;
^ : int option = Some 12

正常に動作していますね。

●問題

逆ポーランド記法で書かれた数式を計算するプログラムを作ってください。数式はリストで表すものとにします。リストの要素は次のように定義します。

type item = Add | Sub | Mul | Div | N of float

演算子は Add (+.), Sub (-.), Mul (*.), Div (/.) で、数値は実数 (float) だけとします。

逆ポーランド記法について簡単に説明します。私達が普通に式を書く場合、1 + 2 のように演算子を真ん中に置きます。この書き方を「中置記法」といいます。このほかに、「前置記法」と「後置記法」という書き方があります。前置記法は演算子を前に置く書き方で、ポーランド記法 (Polish Notation) と呼ばれることもあります。たとえば、1 + 2 であれば + 1 2 と書きます。数式にカッコをつけてみると (+ 1 2) となり、Lisp / Scheme のプログラムになります。

後置記法は演算子を後ろに置く書き方で、逆ポーランド記法 (RPN : Reverse Polish Notation) と呼ばれることもあります。1 + 2 であれば 1 2 + のように書きます。逆ポーランド記法の利点は、計算する順番に演算子が現れるため、カッコが不要になることです。たとえば、1 と 2 の和と 3 と 4 の和との積という数式を表してみましょう。

中置記法 : (1 + 2) * (3 + 4)
後置記法 : 1 2 + 3 4 + *

逆ポーランド記法は、日本語の読み方とまったく同じです。1 2 + で 1 と 2 の和を求め、3 4 + で 3 と 4 を求め、最後に 2 つの結果を掛け算して答えが求まります。

val rpn : rpn list -> float = <fun>

# rpn [N 1.0; N 2.0; N 3.0; Add; Add];;
- : float = 6.
# rpn [N 1.; N 2.; Add; N 3.; N 4.; Add; Mul];;
- : float = 21.
# rpn [N 1.; N 2.; Add; N 3.; N 4.; Sub; Mul];;
- : float = -3.
# rpn [N 1.; N 2.; Add; N 3.; N 4.; Add; N 5.; N 6.; Add; Mul; Mul];;
- : float = 231.

●解答

逆ポーランド記法の数式はスタックを使うと簡単に計算することができます。アルゴリズムは次のようになります。

1. 数値はスタックに追加する。
2. 演算子であればスタックから 2 つ数値を取り出し、演算結果をスタックに追加する。
3. 最後にスタックに残った値が答えになる。

たったこれだけの規則で数式を計算することができます。それでは、実際に 1 2 + 3 4 + * を試してみましょう。次の表を見てください。

スタックはリスト ( ) で表します。最初の 1 と 2 は数値なのでスタックにプッシュします。次は演算子 + なので、スタックからデータを取り出して 1 + 2 を計算します。そして、計算結果 3 をスタックにプッシュします。次に、3 と 4 は数値なのでスタックにプッシュします。その次は演算子 + なので同じように処理して、計算結果 7 をスタックにプッシュします。

スタックの中身は ( 7 3 ) となり、最初の計算結果 3 と次に計算した結果 7 がスタックに格納されています。この状態で最後の * を処理します。7 と 3 を取り出すとスタックは空の状態になります。そして、3 * 7 を計算して 21 をスタックにプッシュします。これで計算は終了です。スタックに残っている値 21 が計算結果となります。

このように、スタックを使うことで逆ポーランド記法で書かれた数式を簡単に計算することができます。実は数式だけではなく、スタックを用いてプログラムを実行することもできます。プログラミング言語 Forth は「数値」と「ワード」という 2 種類のデータしかありません。ワードには +, -, *, / などの演算子のほかに、いろいろな処理が定義されています。もちろん、ユーザが新しいワードを定義することもできます。

Forth の動作は、数値であればスタックにプッシュして、ワードであればそれを実行する、というシンプルなものです。これでプログラミングができるのですから、とてもユニークな言語ですね。

プログラムは次のようになります。

リスト : 数式の計算 (後置記法)

type rpn = Add | Sub | Mul | Div | N of float

let rpn_add = function
  y::x::zs -> (x +. y)::zs
| _ -> [nan]

let rpn_sub = function
  y::x::zs -> (x -. y)::zs
| _ -> [nan]

let rpn_mul = function
  y::x::zs -> (x *. y)::zs
| _ -> [nan]

let rpn_div = function
  y::x::zs -> (x /. y)::zs
| _ -> [nan]

let rpn xs =
  let rec iter expr a =
    match expr with
      [] -> if List.length a = 1 then List.hd a
            else nan
    | (N x)::xs -> iter xs (x::a)
    | Add::xs -> iter xs (rpn_add a)
    | Sub::xs -> iter xs (rpn_sub a)
    | Mul::xs -> iter xs (rpn_mul a)
    | Div::xs -> iter xs (rpn_div a)
  in
    iter xs []

実際の処理は局所関数 iter で行います。引数 expr が数式を表すリストで、引数 a がスタックを表します。expr が空リストになったら、スタックトップの値を返します。このとき、スタックに複数の値が格納されている場合はエラーのかわりに nan を返します。

次に、先頭要素が数値の場合はそれをスタックに追加します。演算子の場合、対応する関数を呼び出します。このとき、最低でも 2 つの値がスタックになければいけません。y::x::xs とマッチングしない場合はエラーのかわりに [nan] を返します。計算するときは、先頭の要素が第 2 引数、2 番目の要素が第 1 引数になることに注意してください。結果はリスト zs の先頭に追加します。

ソート (2)

●マージソート

ソートのお話です。今まで例題としてクイックソートと挿入ソートを取り上げました。データ数を N とすると、挿入ソートの実行時間は N² に比例します。挿入ソートは遅いソートですが、クイックソートは高速なソートで、実行時間は N * log₂ N に比例します。ところがクイックソートにも弱点があり、枢軸の選び方によっては実行時間が N² に比例する遅いソートになってしまいます。リストの場合、枢軸を自由に選ぶことが難しいので、クイックソートはリスト向きのアルゴリズムとはいえません。

そこで、今回はリストに適したソートアルゴリズムである「マージソート (merge sort)」を取り上げます。データ数を N とすると、マージソートの実行時間は N * log₂ N に比例します。マージソートはクイックソートと同様に高速なアルゴリズムですが、実際にプログラムを作って比較してみるとクイックソートの方が高速になります。ただし、クイックソートと違って、データによって性能が劣化することはありません。どのようなデータに対しても力を発揮してくれます。

●リストのマージ

まず最初にマージから説明します。「マージ (併合)」とは、複数のソート済みのリストを一つのソート済みのリストにまとめる操作です。次の図を見てください。

      図 1 : リストのマージ

2 つのリスト a と b があります。これらのリストはソート済みとしましょう。これらのリストをソート済みのリストにまとめることを考えます。a と b はソート済みなので先頭のデータがいちばん小さな値です。したがって、上図のように先頭のデータを比較し、小さい方のデータを取り出して順番に並べていけば、ソート済みのリストにまとめることができます。途中でどちらかのリストが空になったら、残ったリストのデータをそのまま追加します。

それでは、実際にプログラムを作ってみましょう。次のリストを見てください。

リスト 9 : リストのマージ

let rec merge xs ys =
  match (xs, ys) with
    ([], _) -> ys
  | (_, []) -> xs
  | (x1:: xs1, y1::ys1) ->
    if x1 < y1 then x1::merge xs1 ys else y1::merge xs ys1

関数 merge の引数 xs と ys がマージするリストです。最初の節はリスト xs が空リストになった場合で、リスト ys をそのまま返します。2 番目の節はリスト ys が空リストになった場合で、リスト xs をそのまま返します。この 2 つの節が再帰呼び出しの停止条件になります。

リスト xs と ys にデータがあれば、先頭要素 x1 と y1 を比較します。x1 が小さい場合は x1 を、そうでなければ y1 を merge が返すリストに追加します。merge を再帰呼び出しするときは、追加する先頭要素をリストから取り除くことに注意してください。これでリストをマージすることができます。

簡単な実行例を示しましょう。

val merge : 'a list -> 'a list -> 'a list = <fun>

# merge [1; 3; 5; 7] [2; 4; 6; 8];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8]
# merge [10; 20; 30] [1; 2; 3; 4];;
- : int list = [1; 2; 3; 4; 10; 20; 30]

●マージソートの実装

マージソートは、このマージを使ってデータをソートします。次の図を見てください。

 9 5 3 7 6 4 2 8  最初の状態

|5 9|3 7|4 6|2 8| 長さ２の列に併合

|3 5 7 9|2 4 6 8| 長さ４の列に併合 

 2 3 4 5 6 7 8 9  ソート終了


        図 2 : マージソート

マージをソートに応用する場合、最初は各要素をソート済みのリストとして考えます。この状態で隣のリストとマージを行い、長さ 2 のリストを作ります。次に、このリストに対して再度マージを行い、長さ 4 のリストを作ります。このように順番にマージしていくと、最後にはひとつのリストにマージされソートが完了します。

実際にプログラムを作る場合、リストの長さを 1, 2, 4, 8, ... と増やしていくよりも、再帰的に考えた方が簡単です。まず、ソートするリストを 2 つに分割して、前半部分をソートします。次に、後半部分をソートして、その結果をマージすればいいわけです。

再帰呼び出しするたびにリストは 2 つに分割されるので、最後にリストの要素はひとつとなります。これはソート済みのリストなので、ここで再帰呼び出しを終了してマージ処理を行えばいいわけです。プログラムは次のようになります。

リスト 10 : マージソート

(* 先頭から n 個の要素を削除する *)
let rec drop xs n =
  match (xs, n) with
    ((_, 0) | ([], _)) -> xs
  | (_ :: ys, _) -> drop ys (n - 1)

(* マージソート *)
let rec merge_sort n xs =
  match (n, xs) with
    (_, []) -> []
  | (1, x::xs) -> [x]
  | (2, x1::x2::xs) ->
    if x1 < x2 then [x1; x2] else [x2; x1]
  | (_, _) ->
    let m = n / 2 in
    merge (merge_sort m xs) (merge_sort (n - m) (drop xs m))

関数 merge_sort の引数 xs がソートするリスト、引数 n がリストの長さを表します。merge_sort はリストを分割する処理で、新しいリストを作らないことに注意してください。次の図を見てください。

merge_sort はソートするリストの範囲を開始位置と長さで表しています。上図のリストを二分割する場合、前半部分は x と n / 2 で表し、後半部分を y と n / 2 で表します。y はリスト x の先頭から n / 2 個の要素を取り除けば求めることができます。この処理を関数 drop で行います。drop は list の先頭から n 個の要素を取り除きます。リストに対して n 回だけ tl を適用すると考えてもかまいません。簡単な例を示しましょう。

val drop : 'a list -> int -> 'a list = <fun>

# drop [1; 2; 3; 4] 0;;
- : int list = [1; 2; 3; 4]
# drop [1; 2; 3; 4] 2;;
- : int list = [3; 4]
# drop [1; 2; 3; 4] 4;;
- : int list = []

あとは再帰呼び出しでリストを分割していき、リストの長さが 1 になったならば新しいリストを返します。リストの長さが 2 の場合は簡単なので、2 つの要素を比較してソート済みのリストを作成して返します。そして、merge_sort の返り値を merge でマージすればいいわけです。

それでは実行してみましょう。

val merge_sort : int -> 'a list -> 'a list = <fun>

# merge_sort 9 [5; 9; 1; 8; 2; 7; 3; 6; 4];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

正常に動作していますね。

●問題

次の関数を定義してください。

1. リスト xs の中から述語 pred が真を返す最初の要素の位置を求める関数 position_if pred xs
• val position_if : ('a -> bool) -> 'a list -> int option = <fun>
2. リスト xs から述語 pred が真を返す要素の個数を求める関数 count_if pred xs
• val count_if : ('a -> bool) -> 'a list -> int = <fun>
3. リスト xs, ys の直積集合を求める関数 product_set xs ys
• val product : 'a list -> 'b list -> ('a * 'b) list = <fun>
• xs = [1; 2; 3], ys = [4; 5] とすると、直積集合は[(1, 4); (1, 5); (2, 4); (2, 5); (3, 4); (3, 5)]
4. リスト xs のべき集合を求める関数 power_set xs
• val power_set : 'a list -> 'a list list = <fun>
• リスト [1; 2; 3] のべき集合は [[]; [1]; [2]; [3]; [1; 2]; [1; 3]; [2; 3]; [1; 2; 3]]
5. 自然数 n 以下の素数をすべて求める関数 sieve n
• val sieve : int -> int list = <fun>

●解答

リスト : 解答例

let rec position_if pred = function
    [] -> None
  | x::xs -> if pred x then Some x else position_if pred xs

let count_if pred xs =
  let rec count xs a =
    match xs with
      [] -> a
    | y::ys -> count ys (if pred y then a + 1 else a)
  in count xs 0

(* 別解 *)
let count_if1 pred xs =
  List.fold_left (fun a x -> if pred x then a + 1 else a) 0 xs

let flatmap f xs = flatten (List.map f xs)

let product_set xs ys =
  flatmap (fun x -> List.map (fun y -> (x, y)) ys) xs

let rec power_set = function
    [] -> [[]]
  | x::xs -> (power_set xs) @ (List.map (fun ys -> x::ys) (power_set xs))

let rec iota n m =
  if n > m then []
  else n :: iota (n + 1) m

let sieve n =
  let rec sieve_sub xs a =
    match xs with
      [] -> a
    | x::xs as ys ->
       if x * x > n then List.rev_append a ys
       else sieve_sub (List.filter (fun y -> y mod x <> 0) xs) (x::a)
  in sieve_sub (iota 2 n) []

# position_if (fun x -> x mod 2 = 0) [1;2;3;4;5;6;7;8];;
- : int option = Some 2
# position_if (fun x -> x mod 7 = 0) [1;2;3;4;5;6;7;8];;
- : int option = Some 7
# position_if (fun x -> x mod 9 = 0) [1;2;3;4;5;6;7;8];;
- : int option = None

# count_if (fun x -> x mod 2 = 0) [1;2;3;4;5;6;7;8];;
- : int = 4
# count_if (fun x -> x mod 4 = 0) [1;2;3;4;5;6;7;8];;
- : int = 2
# count_if (fun x -> x mod 9 = 0) [1;2;3;4;5;6;7;8];;
- : int = 0

# product_set [1;2;3] [4;5];;
- : (int * int) list = [(1, 4); (1, 5); (2, 4); (2, 5); (3, 4); (3, 5)]
# product_set [1;2;3] [4;5;6];;
- : (int * int) list =
[(1, 4); (1, 5); (1, 6); (2, 4); (2, 5); (2, 6); (3, 4); (3, 5); (3, 6)]

# power_set [1;2;3;4];;
- : int list list =
[[]; [4]; [3]; [3; 4]; [2]; [2; 4]; [2; 3]; [2; 3; 4]; [1]; [1; 4]; [1; 3];
 [1; 3; 4]; [1; 2]; [1; 2; 4]; [1; 2; 3]; [1; 2; 3; 4]]

# sieve 100;;
- : int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
 73; 79; 83; 89; 97]
# sieve 500;;
- : int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
 73; 79; 83; 89; 97; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151;
 157; 163; 167; 173; 179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233;
 239; 241; 251; 257; 263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317;
 331; 337; 347; 349; 353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419;
 421; 431; 433; 439; 443; 449; 457; 461; 463; 467; 479; 487; 491; 499]