Functional Programming

レキシカルスコープ

●レキシカルスコープとダイナミックスコープ

変数の有効範囲を表す用語に「スコープ (scope)」があります。この用語を使うと、厳密ではありませんが、変数の有効範囲は「レキシカルスコープ」と「ダイナミックスコープ」の 2 つに分けることができます。伝統的な Lisp はダイナミックスコープですが、近代的なプログラミング言語、たとえば Common Lisp, Scheme, SML/NJ はレキシカルスコープを採用しています。

それでは、レキシカルスコープについて詳しく見てみましょう。変数 x を表示する関数 foo を定義します。

- val x = "global\n";
val x = "global\n" : string

- fun foo() = print x;
val foo = fn : unit -> unit

- foo();
global
val it = () : unit

関数 foo には局所変数 x を定義していないので、foo を実行した場合は大域変数の値を参照します。その結果 global が表示されます。それでは、foo1 という関数から foo を呼び出す場合を考えてみましょう。foo1 には let で局所変数 x を定義します。この場合、foo はどちらの値を表示するのでしょうか。実際に試してみましょう。

- fun foo1() = let val x = "local\n" in foo() end;
val foo1 = fn : unit -> unit

- foo1();
global
val it = () : unit

大域変数の値 global を表示しました。このように、foo1 で定義した局所変数 x は、foo から参照することはできません。次の図を見てください。

上図では変数の有効範囲を枠で表しています。foo1 の let で定義した局所変数 x は、let の枠の中でのみ有効です。もしも、この枠で変数が見つからない場合は、ひとつ外側の枠を調べます。順番に外側の枠を調べていくと、最後には関数定義の枠に行き着きます。ここで変数（引数）が見つからない場合は大域変数を調べます。

関数 foo は関数定義の枠しかありません。そこに変数 x が定義されていないので、大域変数を調べることになるのです。このように、関数 foo から foo1 の枠と let の枠を超えて変数 x にアクセスすることはできないのです。これを「レキシカルスコープ (lexical scope)」といいます。レキシカルには文脈上いう意味があり、変数が定義されている構造の範囲内 (枠内) でないと、その変数にアクセスすることはできません。

ところが伝統的な Lisp の場合、foo1 で定義した変数 x は呼び出された関数 foo からアクセスすることができます。これを「ダイナミックスコープ (dynamic scope)」といいます。foo1 で定義された変数 x は、foo1 の実行が終了するまで存在し、foo1 から呼ばれた関数ならば、どこからでも参照することができます。もしも、foo1 をダイナミックスコープの処理系、たとえば Emacs Lisp で実行するならば、foo で表示される x の値は local になります。

●レキシカルスコープと局所的な関数

それでは、匿名関数や局所的な関数の場合はどうでしょうか。次の例を見てください。

リスト : リストの要素を n 倍する

fun mapcar(_, nil) = nil
|   mapcar(f, x::xs) = f x :: mapcar(f, xs)

fun times_element(n, l) = mapcar(fn x => x * n, l)  

匿名関数の引数は x だけですから、変数 n は大域変数を参照するように思われるかもしれません。ところが、変数 n は関数 times_element の引数 n を参照するのです。これを図に示すと、次のようになります。

ポイントは、匿名関数が times_element 内で定義されているところです。変数 n は関数の引数として定義されていて、その有効範囲は関数の終わりまでです。匿名関数はその範囲内に定義されているため、変数 n にアクセスすることができるのです。つまり、関数内で定義された匿名関数は、そのとき有効な局所変数にアクセスすることができるのです。

これは let で定義された局所的な関数も同じです。times_element は次のように書き換えることができます。

リスト : リストの要素を n 倍する

fun times_element(n, l) =
  let
    fun timesN x = x * n  
  in
    mapcar(timesN, l)
  end

関数 timesN は times_element 内で定義されているので、timesN から times_element の引数 n を参照することができます。

●クイックソートの改良

簡単な例題として、クイックソートを高階関数に改良してみましょう。データを比較する関数を渡すことで、クイックソートを多相型関数にすることができます。次のリストを見てください。

リスト : クイックソート

fun quicksort(_, nil) = nil
|   quicksort(f, x::xs) =
  let
    (* リストの分割 *)
    fun partition(_, nil, a, b) = (a, b)
    |   partition(z, y::ys, a, b) =
      if f(y, z) then partition(z, ys, y::a, b)  
      else partition(z, ys, a, y::b)

    val (m, n) = partition(x, xs, nil, nil)
  in
    quicksort(f, m) @ (x :: quicksort(f, n))
  end

quicksort の第 1 引数 f がデータを比較する関数、第 2 引数がリストです。リストを分割する関数 partition は quicksort 内で定義しているので、quicksort の引数 f を参照することができます。わざわざ関数 f を partition に渡す必要はありません。なお、partition は末尾再帰でプログラムしています。ご注意ください。

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

val quicksort = fn : ('a * 'a -> bool) * 'a list -> 'a list

- quicksort(op <, [5,9,1,8,2,7,3,6,4]);
val it = [1,2,3,4,5,6,7,8,9] : int list

- quicksort(op >, [5,9,1,8,2,7,3,6,4]);
val it = [9,8,7,6,5,4,3,2,1] : int list

- quicksort(op <, ["c", "a", "d", "e", "b"]);
val it = ["a","b","c","d","e"] : string list

関数型をみると quicksort は多相型関数として定義されていることがわかります。比較関数を渡すことで、データを昇順でも降順でもソートすることができます。

カリー化関数

●クロージャ

Lisp などの関数型言語では、関数を生成する関数を簡単に作ることができます。このとき使われる機能が「クロージャ (closure)」です。クロージャは評価する関数と参照可能な局所変数をまとめたものです。クロージャは関数のように実行することができますが、クロージャを生成するときに参照可能な局所変数を保持するところが異なります。参照可能な局所変数の集合を「環境」と呼ぶことがあります。

SML/NJ でクロージャを生成するには「匿名関数」を使うか、局所的な関数を定義して、その関数を返します。たとえば、「引数を n 倍する関数」を生成する関数は、匿名関数を使うと次のようになります。

- fun foo n = fn x => n * x;
val foo = fn : int -> int -> int

- val foo10 = foo 10;
val foo10 = fn : int -> int
- foo10 100;
val it = 1000 : int

- val foo5 = foo 5;
val foo5 = fn : int -> int
- foo5 11;
val it = 55 : int

関数 foo は引数を n 倍する関数を生成します。関数 foo の型 int -> int -> int は int -> (int -> int) を意味し、引数 int を受け取り int -> int という関数を返すことを表しています。-> は四則演算とは違って右結合になります。

変数 foo10 に foo 10 の返り値をセットします。すると、foo10 は引数を 10 倍する関数として使うことができます。同様に、変数 foo5 に foo 5 の返り値をセットすると、foo5 は引数を 5 倍する関数になります。

匿名関数を生成するとき、評価する関数のほかに、そのとき参照可能な局所変数、つまり「環境」もいっしょに保存されます。この場合、参照可能な局所変数は foo の引数 n です。そして、クロージャを実行するときは、保存されている局所変数を参照することができるのです。

foo 10 を実行して無名関数を生成するとき、定義されている局所変数は n で、その値は 10 ですね。この値がクロージャに保存されているので、foo10 の関数は引数を 10 倍した結果を返します。foo 5 を評価すると n の値は 5 で、それがクロージャに保存されているので、foo5 の関数は引数を 5 倍した結果を返すのです。

また、let で局所的な関数を定義して、その関数を返すとクロージャを生成することができます。let を使った例を示します。

- fun foo n = let fun bar x = n * x in bar end;
val foo = fn : int -> int -> int

- val foo100 = foo 100;
val foo100 = fn : int -> int
- foo100 11;
val it = 1100 : int

let で関数 bar を定義して、bar を返します。すると、foo は「引数を n 倍する関数」を生成する関数になります。

●補足

クロージャを理解する場合、環境を連想リストで考えるとわかりやすいと思います。通常、関数を呼び出す場合、関数を評価するための環境は空リストです。最初に、引数がこの環境に追加されます。let で定義される局所変数もこの環境に追加されます。もしも、環境に該当する変数が存在しない場合は大域変数を参照します。

たとえば、foo 5 と呼び出すと環境は次のようになります。

foo( 5 ) ==> 環境 : [(n, 5)]

連想リストの n が変数名で、その値が 5 です。クロージャを生成するとき、この連想リストを保持すると考えてください。そして、クロージャを評価するときは、保存していた環境を使います。したがって、foo5 11 を評価すると、環境 [(n, 5)] に引数 x の値が追加され、[(x, 11), (n, 5)] になります。この環境で式 n * x を評価するので、5 * 11 = 55 を返すわけです。

関数の評価が終了すると、環境に追加された変数は削除されます。foo5 11 の評価で追加された変数は x なので、(x, 11) が削除され [(n, 5)] になります。このように、クロージャに保存された環境は変化しません。

ただし、Lisp や Scheme のように、変数の値を書き換えることができる処理系では、クロージャに保存された変数の値を変更することが可能です。興味のある方は Common Lisp 入門 : レキシカルスコープとクロージャ をお読みください。

●カリー化関数

クロージャは Lisp でも使える方法です。ところが、SML/NJ にはもっと簡単な方法が用意されています。それは関数を「カリー化形式 (Curried form)」で定義することです。これを「カリー化関数」といいます。次の例を見てください。

- fun bar x y = x * y;
val bar = fn : int -> int -> int
- bar 10 11;
val it = 110 : int

- val bar10 = bar 10;
val bar10 = fn : int -> int
- bar10 1000;
val it = 10000 : int
- val bar5 = bar 5;
val bar5 = fn : int -> int
- bar5 111;
val it = 555 : int

関数をカリー化する場合、引数をカッコで囲わず、カンマでも区切りません。関数 bar の型を見ると int -> int -> int になっていますね。これで引数を一つだけ与えれば、関数を返すことになります。もちろん、引数を 2 つ与えれば、それらを乗算した結果を返します。これは、最初の引数を受け取って関数を生成し、その関数を 2 番目の引数に適用する、という動作になります。SML/NJ の場合、カリー化関数はよく使われる方法です。

●高階関数のカリー化

関数のカリー化は高階関数でも行うことができます。たとえば、mapcar をカリー化すると次のようになります。

リスト : mapcar のカリー化

fun mapcar_c _ nil = nil
|   mapcar_c f (x::xs) = f x :: mapcar_c f xs  

関数 mapcar_c は mapcar をカリー化したものです。カリー化関数の引数は空白で区切るだけなので、パターン x::xs はカッコで囲む必要があります。実際に mapcar_c を定義すると次のようになります。

val mapcar_c = fn : ('a -> 'b) -> 'a list -> 'b list

カリー化により mapcar の関数型は ('a -> 'b) * 'a list の部分が ('a -> 'b) -> 'a list に変わっています。つまり、関数型 'a -> 'b を引数に受け取り、'a list -> 'b list という関数を返すことが示されています。次の実行例を見てください。

- val foo = mapcar_c (fn x => x * x);
val foo = fn : int list -> int list
- foo [1,2,3,4,5];
val it = [1,4,9,16,25] : int list

- mapcar_c (fn x => x * x) [1,2,3,4,5];
val it = [1,4,9,16,25] : int list

mapcar_c に値を 2 乗する関数を渡すと、リストの要素を 2 乗する関数を生成することができます。この関数を変数 foo に束縛し、リストに foo を適用すると要素が 2 乗されたリストが返されます。もちろん、mapcar_c に関数とリストを渡して評価することもできます。

SML/NJ で用意されいる高階関数のほとんどがカリー化されています。ここで、代表的な高階関数を紹介しましょう。

val map : ('a -> 'b) -> 'a list -> 'b list
val app : ('a -> unit) -> 'a list -> unit

map は mapcar_c と同じくマッピングを行う関数です。app は副作用を伴う関数を受け取り、それをリストの要素に適用します。リストの要素を出力するときに便利です。簡単な実行例を示します。

- val squareList = map (fn x => x * x);
val squareList = fn : int list -> int list
- squareList [1,2,3,4,5];
val it = [1,4,9,16,25] : int list

- val printIntlist = app (fn x => print(Int.toString(x)^"\n"));
val printIntlist = fn : int list -> unit
- printIntlist [1,2,3,4,5];
1
2
3
4
5
val it = () : unit

map に fn x => x * x を渡すと、リストの要素を 2 乗する関数を作成することができます。map の返り値を変数 squareList に束縛すると、squareList はリストの要素を 2 乗する関数として使うことができます。同様に、app に整数を表示する関数を渡して返り値を printIntlist に束縛すると、printIntlist は int list を表示する関数になります。

val foldr : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
val foldl : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

foldr と foldl は 高階関数 で説明した畳み込み (fold_left, fold_right) と同じ働きをする関数です。foldr と foldl の動作は次のようになります。

foldr f g  [a1, a2, a3, ..., an-1, an] => f( a1, f( a2, f( a3, ..., f( an, g ) ... )))
foldl f g  [a1, a2, a3, ..., an-1, an] => f( an, f( an-1, f( an-2, ..., f( a1, g ) ... )))

foldl の動作は 高階関数 で説明した fold_left の動作と少し異なります。SML/NJ の場合、foldl f g list は foldr f g (rev list) と同じになります。rev はリストを反転する SML/NJ の関数です。簡単な例を示します。

- fun count_if f l = foldr (fn(x, y) => if f x then y + 1 else y) 0 l;
val count_if = fn : ('a -> bool) -> 'a list -> int

- count_if (fn(x) => x >= 10) [1,11,2,12,3,13,4];
val it = 3 : int

- fun remove_if f l = foldr (fn(x, y) => if f x then y else x::y) nil l;
val remove_if = fn : ('a -> bool) -> 'a list -> 'a list

- remove_if (fn(x) => x mod 2 = 0) [1,2,3,4,5,6];
val it = [1,3,5] : int list

foldr を使って関数 count_if を定義します。count_if は引数の述語が真となる要素の個数を数える関数です。匿名関数 fn(x, y) の引数 x がリストの要素、y が条件を満たした要素の個数になります。f x が真ならば y + 1 を返し、そうでなければ y を返します。これで条件を満たす要素をカウントすることができます。

次は関数 remove_if を定義します。remove_if は述語 f が真となる要素を削除する関数です。匿名関数 fn(x, y) で、f x が真であれば y をそのまま返し、そうでなければ x を y のリストに追加します。これで条件を満たす要素を削除することができます。

SML/NJ の場合、リストを操作する関数はストラクチャ List に定義されています。その中から filter, find, exists, all を説明します。

val filter : ('a -> bool) -> 'a list -> 'a list
val find   : ('a -> bool) -> 'a list -> 'a option
val exists : ('a -> bool) -> 'a list -> bool
val all    : ('a -> bool) -> 'a list -> bool

filter は 高階関数 で説明した「フィルター」と同じ働きをする関数です。filter pred l は述語 pred が真となる要素をリストに格納して返す関数で、remove_if と逆の働きをします。find pred l は述語 pred が真となる要素を探す関数です。exists pred l は述語 pred を満たす要素が一つでもあれば真を返し、そうでない場合は偽を返します。逆に、all pred l は全ての要素が述語 pred を満たせば真を返し、述語 pred を満たさない要素が一つでもあれば偽を返します。簡単な使用例を示します。

- List.filter (fn x => x >= 10 andalso x < 20) [1,5,10,15,20,25];
val it = [10,15] : int list

- List.find (fn x => x mod 2 = 0) [1,5,10,15,20];
val it = SOME 10 : int option

- List.exists (fn x => x mod 2 = 0) [1,5,10,15];
val it = true : bool

- List.all (fn x => x mod 2 = 0) [2,4,6,8,10];
val it = true : bool

●関数の合成

関数 f(x) と g(x) を合成して新しい関数 h(x) を作ることを考えてみましょう。関数 h(x) を次のように定義します。

h(x) = g( f(x) )

関数 f(x) の返り値が関数 g(x) の引数になるので、関数 g(x) が受け付ける値でなければいけません。そうでないと関数を合成することはできません。この条件を SML/NJ の型で表すと、次のようになります。

g : 'a -> 'b,  f : 'c -> 'a,  h : 'c -> 'b

関数 f の返り値が型 'a ならば、関数 g の引数も型は 'a でなければいけません。SML/NJ の場合、関数を合成する演算子 o が用意されています。演算子 o の型を示します。

- op o;
val it = fn : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b

演算子 o は 2 つの関数を受け取り、それらを合成した関数を返します。'a -> 'b が関数 g で、'c -> 'a が関数 f になります。そして、関数 f と g を合成した新しい関数 'c -> 'b を返します。簡単な例を示しましょう。

- fun foo x = 2 * x + 1;
val foo = fn : int -> int
- fun bar y = y * y + 3 *y;
val bar = fn : int -> int
- bar( foo( 4 ) );
val it = 108 : int

- val baz = bar o foo;
val baz = fn : int -> int
- baz 4;
val it = 108 : int
- (bar o foo) 4;
val it = 108 : int

関数 foo と bar を定義します。foo と bar の合成は bar( foo( x ) ) と表すことができます。実際に 4 を計算すると 108 になります。これらの関数は bar o foo で合成することができます。その値を変数 baz に束縛すると、baz を合成関数として使うことができます。また、最後の例のように、合成関数 (bar o foo) をそのまま使うこともできます。

もちろん、高階関数も合成することができます。リストの要素を 2 乗して、10 以上の値を取り出す関数は、filter と map を合成すると簡単に作ることができます。

- val foo = (List.filter (fn x => x >= 10)) o (map (fn x => x * x));
val foo = fn : int list -> int list
- foo [1,2,3,4,5];
val it = [16,25] : int list

このように、SML/NJ は関数を柔軟に操作することができます。

パターンと照合

●case

パターンは Common Lisp の cond や case のような条件分岐にも使うことができます。SML/NJ には case 式が用意されています。

case expr of pat1 => expr1 | pat2 => expr2 | ..... | patN => exprN

pat はパターン (pattern) のことです。pat => expr を「規則」といい、複数の規則を縦線 ( | ) でつないだものを「照合」といいます。最初に case は式 expr を評価します。その結果とマッチングするパターンの規則を選択し、対応する式を評価します。そして、その結果が case 式の返り値となります。

なお、一度規則が選択されたら、それ以降の規則は選択されません。それから、規則の式 expr1, ..., exprN の返り値は同じデータ型でなければいけません。ご注意ください。

簡単な例を示します。

- fun foo n =
=   case n
=     of 0 => print "0\n" 
=      | 1 => print "1\n"
=      | _ => print "other\n";
val foo = fn : int -> unit

- foo 0;
0
val it = () : unit
- foo 1;
1
val it = () : unit
- foo 2;
other
val it = () : unit

匿名変数はどんな値でもマッチングします。したがって、他の規則が選択されない場合でも、最後の規則は必ず選択されることになります。

case 式のパターンには変数を使うことができます。変数は局所変数として扱われ、有効範囲は対応する規則の式の中だけになります。たとえば、リストの要素を削除する関数 remove_if を case を使って記述すると次のようになります。

リスト : 関数 remove_if

fun remove_if(f, x) =
  case x
    of nil => nil
     | y::ys => if f y then remove_if(f, ys)  
                else y :: remove_if(f, ys)

実行例を示します。

val remove_if = fn : ('a -> bool) * 'a list -> 'a list

- remove_if(fn x => x mod 2 = 0, [1,2,3,4,5,6] );
val it = [1,3,5] : int list

このように、関数の定義とよく似た形式になります。実をいうと、SML/NJ は照合を使って関数を定義することができるのです。

●照合による関数の定義

fun を使わずに関数 f を定義する場合、照合を使って次のように行います。

val rec f = fn pat1 => expr1 | pat2 => expr2 | ... | patN => exprN

照合による関数の定義は匿名関数と同じ形式です。匿名関数は規則が一つしかない特別な場合に相当します。rec は再帰呼び出しをする場合に限り必要になります。たとえば、関数 remove_if は次のようになります。

リスト : 関数 remove_if

val rec remove_if = fn
       (_, nil) => nil |
     (f, x::xs) => if f x then remove_if(f, xs) 
                   else x::remove_if(f, xs);

実行例を示します。

val remove_if = fn : ('a -> bool) * 'a list -> 'a list

- remove_if( fn(x) => x mod 2 = 0, [1,2,3,4,5,6] );
val it = [1,3,5] : int list

このように、照合を使っても関数を定義することができます。一般的には、fun を使って関数を定義した方が簡単だと思います。

●as

パターン x::xs を使うとリストを分解することができますが、分解した値 x や xs だけではなく、元のリストの値を参照したいときがあります。このような場合、as を使うと変数とパターンを同時に設定することができます。

識別子 as パターン

たとえば、a as x::xs と [1, 2, 3] をマッチングさせると、次のようになります。

a  -> [1, 2, 3]
x  -> 1
xs -> [2, 3]

このように、パターン x::xs とマッチングした場合、変数 a の値は分解する前の [1, 2, 3] になります。

●挿入ソート

それでは簡単な例題として、「挿入ソート (insert sort)」を作ってみましょう。挿入ソートの考え方はとても簡単です。ソート済みのリストに新しいデータを挿入していくことでソートを行います。たとえば、リスト [2, 4, 6] に 5 を挿入する場合、リストの要素 n と 5 を順番に比較して、5 < n を満たす位置に 5 を挿入すればいいわけです。この場合は、4 と 6 の間に 5 を挿入すればいいですね。

ソートするリストは、tl で分解していくと空リストになります。これをソート済みのリストと考えて、ここにデータを挿入していきます。データを比較する関数は引数として渡せばいいでしょう。プログラムは次のようになります。

リスト : 挿入ソート

fun insert_sort(_, nil) = nil
|   insert_sort(f, y::ys) =
  let
    fun insert_element(n, nil) = [n]
    |   insert_element(n, a as x::xs) =
      if f(n, x) then n::a else x::insert_element(n, xs)  
  in
    insert_element(y, insert_sort(f, ys))
  end

関数 insert_sort は引数のリストを再帰呼び出しで分解します。insert_sort を再帰呼び出ししてリスト ys をソートし、そのリストに先頭要素 y を関数 insert_element で挿入します。

関数 insert_element は再帰呼び出しでリストをたどり、データ n を挿入する位置を探します。述語 f の返り値が真であれば、その位置にデータを挿入します。ここで、a as x::xs の変数 a を使っています。n::a とすることでリストに n を挿入することができます。

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

val insert_sort = fn : ('a * 'a -> bool) * 'a list -> 'a list

- insert_sort(op <, [9, 1, 8, 2, 7, 3, 6, 4, 5]);
val it = [1,2,3,4,5,6,7,8,9] : int list

挿入ソートはデータ数が多くなると実行時間がかかります。データ数を N とすると、実行時間は N の 2 乗に比例します。挿入ソートは簡単ですが遅いアルゴリズムなのです。

●マージソート

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

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

●リストのマージ

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

      図 : リストのマージ

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

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

リスト : リストのマージ

fun merge(_, nil, n) = n
|   merge(_, m, nil) = m
|   merge(f, m as x::xs, n as y::ys) =
  if f(x, y) then x::merge(f, xs, n) else y::merge(f, m, ys)  

関数 merge の引数 f がデータを比較する述語、m と n がマージするリストです。最初の定義はリスト m が空リストになった場合で、リスト n をそのまま返します。2 番目の定義はリスト n が空リストになった場合で、リスト m をそのまま返します。この 2 つが再帰呼び出しの停止条件になります。

リスト m と n にデータがあれば、先頭要素 x と y を述語 f で比較します。f が真であれば x を、そうでなければ y を merge が返すリストに追加します。merge を再帰呼び出しするときは、追加する先頭要素をリストから取り除くことに注意してください。これでリストをマージすることができます。

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

- merge(op <, [1, 3, 5, 7], [2, 4, 6, 8]);
val it = [1,2,3,4,5,6,7,8] : int list

- merge(op <, [10, 20, 30], [1, 2, 3, 4]);
val it = [1,2,3,4,10,20,30] : int list

●マージソートの実装

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

  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 のリストを作ります。次に、このリストに対して再度マージを行い、長さ 4 のリストを作ります。このように順番にマージしていくと、最後にはひとつのリストにマージされソートが完了します。

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

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

リスト : マージソート

fun merge_sort(_, nil, _) = nil
|   merge_sort(_, x::xs, 1) = [x]
|   merge_sort(f, x1::x2::xs, 2) = 
  if f(x1, x2) then [x1, x2] else [x2, x1]
|   merge_sort(f, x, n) =
  let
    val m = n div 2
  in
    merge(f, merge_sort(f, x, m),
             merge_sort(f, List.drop(x, m), n - m))  
  end

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

merge_sort はソートするリストの範囲を開始位置と長さで表しています。上図のリストを二分割する場合、前半部分は x と n / 2 で表し、後半部分を y と n / 2 で表します。y はリスト x の先頭から n / 2 個の要素を取り除けば求めることができます。この処理は SML/NJ に用意されている関数 drop を使うと簡単です。

List.drop(list, n)

drop は list の先頭から n 個の要素を取り除きます。list に対して n 回だけ tl を適用すると考えてもかまいません。簡単な例を示しましょう。

- List.drop( [1,2,3,4], 0 );
val it = [1,2,3,4] : int list
- List.drop( [1,2,3,4], 2 );
val it = [3,4] : int list
- List.drop( [1,2,3,4], 4 );
val it = [] : int list

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

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

- merge_sort(op <, [5,9,1,8,2,7,3,6,4], 9);
val it = [1,2,3,4,5,6,7,8,9] : int list
- merge_sort(op >, [5,9,1,8,2,7,3,6,4], 9);
val it = [9,8,7,6,5,4,3,2,1] : int list

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