Functional Programming

二分探索木

今回はデータ構造の簡単な例題として「二分探索木 (binary search tree)」を取り上げます。Haskell には二分木 (平衡木) を使ったモジュール Data.Map と Data.Set が用意されているので、わざわざ二分木を自作する必要はないのですが、今回は Haskell のお勉強ということで、あえてシンプルな二分木を実際に作ってみましょう。

あるデータの中から特定のデータを探す場合、データ数が少なければ力任せに探索してもなんとかなりますが、データ数が多くなると探索に時間がかかるようになります。このような場合、あらかじめデータを整理整頓しておくことで、特定のデータを高速に見つけることができるようになります。この代表的なアルゴリズムが「ハッシュ法」と「二分探索木」です。

二分探索木はその名が示すように「木構造」の一種です。まずは木構造から説明しましょう。二分木を理解されている方は読み飛ばしてもらってかまいません。

次へ

●木構造

「木構造 (tree structer)」は「木 (tree)」とも呼ばれるデータ構造で、「節 (ノード)」と呼ばれる要素に対して、階層的な関係を表したものです。身近な例では、ディレクトリの階層構造が木にあたります。ディレクトリに「ルートディレクトリ」があるように、木にも「根 (ルート)」と呼ばれる節が存在します。

          図 : 一般的な木構造の一例

木を図示する場合、階層関係がはっきりわかるように、根を上にして、同じ階層にある節を並べて書きます。根からレベル 0、レベル 1 と階層を数えていき、最下層の節までの階層数を「木の高さ」といいます。木は、ある節から下の部分を切り出したものも、木としての性質を持っています。これを「部分木」といいます。

木は、ある節からほかの節に至る「経路」を考えることができます。たとえば、A から J には、A - B - G - J という経路がありますね。これは、ディレクトリやファイルを指定するときのパスと同じです。

ある節から根の方向にさかのぼるとき、途中で通っていく節を「先祖」といい、直接繋がっている節を「親」といます。これは、逆から見ると「子孫」と「子」という関係になります。子を持たない節をとくに「葉」と呼ぶことがあります。上図でいうと、G は J と K の親で、J は G の子になります。J は子を持っていないので葉となります。

子は、「左 < 右」の順番で節に格納するのが一般的です。これを「順序木」といいます。また、順番がない木を「無順序木」と呼びます。節が持っている子の数を「次数」といいます。上図の場合、A は 3 つの子 B, C, D を持っているので、A の次数は 3 となります。すべての節の次数を n に揃えた順序木を「 n 分木」と呼びます。

●二分木

とくに、次数が 2 の二分木は、プログラムでよく使われるデータ構造です。

               図 : 二分木の一例

上図に二分木の例を示します。二分木では、節にひとつのデータを格納します。そして、その節の左側の子には小さいデータを、右側の子には大きいデータが配置されるように木を構成します。

この二分木をデータの探索に使うアルゴリズムが「二分探索木」です。二分探索木はデータの探索・挿入を高速に行うことができます。たとえば、上図の木から 19 を探してみましょう。まず root の 18 と比較します。18 < 19 ですから、右側の子をたどり 22 と比較します。今度は 19 < 22 なので左側の子をたどります。次は 20 と比較し 19 < 20 なので左側の子をたどり、ここで 19 を見つけることができます。

二分探索木の探索は「二分探索 (binary search)」と同じ原理です。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。上図の場合でも、探索するデータ数が 15, 7, 3, 1 となり、最後に見つけることができました。

データ数を N とすると、単純な線形探索では平均で N / 2 回の比較が必要になりますが、二分探索木を使うと log₂ N 程度の回数で収まります。たとえば、データが 100個ある場合、線形探索では 50 回データを比較しなければいけないのに、二分探索木では 7 回程度の比較で済むわけです。ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分探索木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。

そこで、左右のバランスを一定の範囲に収める「平衡木」が考案されています。有名なところでは AVL 木、赤黒木 (red-black tree)、2-3 木、B 木、B* 木などがあります。拙作のページ Algorithms with Python では、AVL 木、赤黒木、2-3 木など平衡木のアルゴリズムを詳しく説明しています。興味のある方はお読みください。今回は Haskell のお勉強ということで、シンプルな二分探索木をプログラムすることにします。なお、本稿では二分探索木のことを単に「二分木」と書くことにします。

●二分木の実装

それでは、Haskell で二分木を作ってみましょう。最初に data 宣言で二分木を定義します。

リスト : 二分木の定義

data Tree a = Nil | Node a (Tree a) (Tree a) deriving Show

二分木のデータ型は Tree a とします。Nil が空の木を表し、Node が節を表します。Node の第 1 要素が二分木に格納するデータ、第 2 要素が左部分木、第 3 要素が右部分木を表します。簡単な例を示します。

これを図で表すと次のようになります。

●データの探索

それでは、データを探索する関数から作ってみましょう。この処理はデータを比較して左右の部分木をたどっていくだけです。

リスト : データの探索

search :: Ord a => a -> Tree a -> Maybe a
search _ Nil = Nothing
search x (Node y l r)
  | x == y    = Just y
  | x < y     = search x l
  | otherwise = search x r

関数 search の第 1 引数 x が探索するデータ、第 2 引数が二分木です。二分木が Nil であれば、これ以上探索することはできません。データは見つからなかったので Nothing を返します。そうでなければ、引数 x と節のデータを比較します。節のデータはパターンマッチングで取り出すことができます。y がデータ、l が左部分木、r が右部分木です。x == y ならばデータが見つかったので Just y を返します。x < y ならば search を再帰呼び出しして左部分木をたどります。そうでなければ x > y なので右部分木をたどります。

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

*Tree> a = Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil))
*Tree> a
Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil))
*Tree> search 0 a
Nothing
*Tree> search 1 a
Just 1
*Tree> search 2 a
Just 2
*Tree> search 3 a
Just 3
*Tree> search 4 a
Just 4
*Tree> search 5 a
Just 5
*Tree> search 6 a
Just 6
*Tree> search 7 a
Just 7
*Tree> search 8 a
Nothing

●最小値と最大値

二分木の場合、最小値と最大値は簡単に求めることができます。左側の子を順番にたどっていき、左側の子がない節に行き着いたとき、その節のデータが最小値になります。逆に、右側の子を順番にたどっていき、右側の子がない節に行き着いたとき、その節のデータが最大値になります。

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

リスト : 最小値と最大値

-- 最小値を求める
searchMin :: Tree a -> Maybe a
searchMin Nil = Nothing
searchMin (Node x Nil _) = Just x
searchMin (Node _ l   _) = searchMin l

-- 最大値を求める
searchMax :: Tree a -> Maybe a
searchMax Nil = Nothing
searchMax (Node x _ Nil) = Just x
searchMax (Node _ _ r)   = searchMax r

関数 searchMin は最小値を求めてそれを返します。空の木の場合は Nothing を返します。次に、左側の子の値をチェックします。もし、Nil であれば左側の子がないので、その節のデータが最小値です。格納されているデータ x を Just に格納して返します。そうでなければ、searchMin を再帰呼び出しして左側の子をたどります。関数 searchMax は最大値を求めてそれを返します。右側の子をたどり、右側の子が Nil の節のデータを返します。

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

*Tree> a
Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil))
*Tree> searchMin a
Just 1
*Tree> searchMax a
Just 7

●データの挿入

次は、データを挿入する関数を作りましょう。探索と同様に、データを比較して木をたどっていき、木がなくなった所に新しいデータを挿入します。

リスト : データの挿入

-- 要素が一つの木
singleton :: a -> Tree a
singleton x = Node x Nil Nil

-- データの挿入
insert :: Ord a => a -> Tree a -> Tree a
insert x Nil = singleton x
insert x (Node y l r)
  | x == y    = Node x l r
  | x < y     = Node y (insert x l) r
  | otherwise = Node y l (insert x r)

関数 insert の第 1 引数 x が挿入するデータ、第 2 引数が二分木です。二分木が Nil であれば、関数 singleton で新しい節を作って返します。この返り値を節の部分木にセットします。2 番目の節で、x と y が等しい場合は二分木に同じデータがあるので新しい節 Node x l r に置き換えます。x < y であれば、insert を再帰呼び出しして左部分木をたどります。そして、左部分木を insert x l の返り値に置き換えた節を新しく作って返します。

Haskell は純粋な関数型言語なので、手続き型言語のように節のデータを書き換えることはできません。insert の返り値を格納するため新しい節を作って、それを返すことになります。もしも、l が Nil であれば、ここに新しい節が挿入され、新しい部分木が返されます。x > y であれば右部分木をたどり、データを挿入した新しい右部分木を返します。

insert のほかに、リストから二分木を生成する関数があると便利です。次のリストを見てください。

リスト : リストから二分木を作る

fromList :: Ord a => [a] -> Tree a
fromList xs = foldl (flip insert) Nil xs

関数 fromList は畳み込み foldl を使うと簡単です。初期値に空の木 Nil を与え、リスト xs から要素を順番に取り出して、insert で二分木に追加していくだけです。flip は引数の順番を交換する関数です。

*Main> :t flip
flip :: (a -> b -> c) -> b -> a -> c

foldl の場合、呼び出す関数に渡す引数は、最初が累積変数で次がリストの要素です。insert の引数は逆になっているので、flip を使って合わせています。

簡単な実行例を示します。

*Tree> b = Nil
*Tree> c = insert 4 b
*Tree> c
Node 4 Nil Nil
*Tree> d = insert 2 c
*Tree> d
Node 4 (Node 2 Nil Nil) Nil
*Tree> e = insert 6 d
*Tree> e
Node 4 (Node 2 Nil Nil) (Node 6 Nil Nil)
*Tree> f = fromList [4,2,1,3,6,7,5]
*Tree> f
Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil))

●データの削除

次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが「葉」の場合は、それを削除するだけなので簡単ですが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。最初に、葉を削除する場合を説明します。下図を見てください。

                図 : データの削除 (葉の場合)

15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。

次に、子が一つある場合を考えてみましょう。

             図 : データの削除 (子が一つの場合)

16 を削除する場合、その子である 15 と置き換えれば二分木の構成は保たれます。これも簡単ですね。問題は、子が二つある節を削除する場合です。

             図 : データの削除 (子が二つの場合)

この場合、削除するデータの右部分木の中から最小値のデータ ^[*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。たとえば、上図で 14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。

●最小値と最大値の削除

まずは木の中から最小値と最大値の節を削除する関数を作成しましょう。次のリストを見てください。

リスト : 最小値と最大値の削除

-- 最小値の削除
deleteMin :: Tree a -> Tree a
deleteMin Nil = Nil
deleteMin (Node _ Nil r) = r
deleteMin (Node x l   r) = Node x (deleteMin l) r

-- 最大値の削除
deleteMax :: Tree a -> Tree a
deleteMax Nil = Nil
deleteMax (Node _ l Nil) = l
deleteMax (Node x l r)   = Node x l (deleteMax r)

関数 deleteMin は最小値を格納している節を削除します。左側の子が Nil の節を探すのは searchMin と同じです。見つけたら、もう一つの子 r を返します。そうでなければ、deleteMin を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、その返り値を格納した新しい節を返します。これで、最小値を持つ節が削除されます。葉の場合であれば r は Nil なので、単純に削除されることになります。

関数 deleteMax は最大値を格納している節を削除します。右側の子が Nil の節を探して、見つけたら左側の子 r を返します。そして、その返り値を格納した新しい節を返します。

●データ削除のプログラム

それでは、データを削除する関数 delete を作ります。まず削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。

リスト : データの削除

delete :: Ord a => a -> Tree a -> Tree a
delete x Nil = Nil
delete x (Node y l r)
  | x < y     = Node y (delete x l) r
  | x > y     = Node y l (delete x r)
  | otherwise = delete' l r where
      delete' Nil r = r
      delete' l Nil = l
      delete' l r = Node x' l (deleteMin r)
        where Just x' = searchMin r

まず、節が Nil ならばデータが見つからなかったので Nil をそのまま返します。次に、削除するデータ x と節のデータ y を比較します。x と節のデータ y が等しくない場合は、左右の部分木をたどって削除するデータを探索します。この処理は今までと同じで、delete の返り値を格納した新しい節を返します。

等しい場合はその節を削除します。この処理を局所関数 delete' で行います。l が Nil の場合は r を返し、r が Nil の場合は l を返します。子が 2 つある場合は、右部分木の最小値を関数 searchMin で求め、その値を格納した新しい節を作ります。このとき、関数 deleteMin で最小値を格納していた節を削除します。これで、削除するデータを最小値で置き換えることができます。

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

*Tree> a
Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil))
*Tree> delete 4 a
Node 5 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 Nil (Node 7 Nil Nil))
*Tree> delete 2 a
Node 4 (Node 3 (Node 1 Nil Nil) Nil) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil))
*Tree> delete 6 a
Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 7 (Node 5 Nil Nil) Nil)
*Tree> foldl (flip delete) a [1..7]
Nil

●二分木の巡回

次は、二分木の全データにアクセスする関数を作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。「木」のすべての節を規則的な順序で回ることを「巡回 (traverse)」といいいます。このなかで、次の 3 つの方法が重要です。

1. 行きがけ順 (pre-order)
   まず節のデータを出力、その後左の子、右の子の順番で出力する。
2. 帰りがけ順 (post-order)
   左の子、右の子と出力してから、節のデータを出力する。
3. 通りがけ順 (in-order)
   左の子を出力、次に節のデータを出力、最後に右の子を出力する。

名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。

二分木の巡回は、再帰定義を使えば簡単に実現できます。プログラムは次のようになります。

リスト : 二分木をリストに変換する (通りがけ順)

toList :: Tree a -> [a]
toList Nil = []
toList (Node x l r) = toList l ++ [x] ++ toList r

-- 別解
toList :: Tree a -> [a]
toList tree = iter tree [] where
  iter Nil xs = xs
  iter (Node x l r) xs = iter l (x : iter r xs)

関数 toList は二分木を通りがけ順で巡回し、要素をリストに格納して返します。木が Nil であれば空リストを返します。そうでなければ、toList を再帰呼び出しして左部分木を巡回し、次に右部分木を巡回します。あとはその返り値を [x] をはさんで演算子 ++ で連結するだけです。

別解は演算子 ++ を使わないでプログラムしたものです。局所関数 iter の第 2 引数を累積変数として使います。ここに二分木の要素を追加していきます。要素はリストの先頭に追加されていくので、左部分木からたどるとリストの要素は逆順になります。このため、右部分木からたどることに注意してください。

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

*Tree> a
Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil))
*Tree> toList a
[1,2,3,4,5,6,7]

●二分木の畳み込み

最後に、二分木を畳み込む関数 fold_left と fold_right を作りましょう。

リスト : 畳み込み

fold_left :: (a -> b -> a) -> a -> Tree b -> a
fold_left _ a Nil = a
fold_left f a (Node x l r) = fold_left f (f (fold_left f a l) x) r

fold_right :: (a -> b -> b) -> b -> Tree a -> b
fold_right _ a Nil = a
fold_right f a (Node x l r) = fold_right f (f x (fold_right f a r)) l

今回は通りがけ順で畳み込みを行うことにします。fold_left は左部分木から、fold_right は右部分木から順番にたどります。木が Nil の場合は引数 a をそのまま返します。そうでなければ fold_left (fold_right) を再帰呼び出します。関数 f を適用するとき、fold_left であれば左部分木を畳み込みした結果と x を渡します。fold_right は x と右部分木を畳み込みした結果を渡します。これで二分木を畳み込むことができます。

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

*Tree> a
Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil))
*Tree> fold_left (flip (:)) [] a
[7,6,5,4,3,2,1]
*Tree> fold_right (:) [] a
[1,2,3,4,5,6,7]
*Tree> fold_right (\_ a -> a + 1) 0 a
7
*Tree> fold_right (const (+1)) 0 a
7

const は次に示す型を持つ関数です。

const :: a -> b -> a

a -> b -> a は a -> (b -> a) のことなので、const a で生成される関数は、どのような引数を与えても、a を返す関数になります。次の例を見てください。

*Tree> c10 = const 10
*Tree> :t +d c10
c10 :: b -> Integer
*Tree> c10 20
10
*Tree> c10 30
10

const 10 で生成された関数 c10 は、どんな引数が渡されても 10 を返す関数となります。ここで、const に型 a -> c の関数を渡す場合を考えてみましょう。型は次のようになります。

(a -> c) -> (b -> (a -> c)) => (a -> c) -> (b -> a -> c)

生成される関数は b -> a -> c になります。これは第 1 引数を無視して、第 2 引数の値に対して関数を適用することになります。

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

*Tree> add1 = const (+1)
*Tree> :t +d add1
add1 :: b -> Integer -> Integer
*Tree> add1 1 2
3
*Tree> add1 10 2
3

このように、const (+1) で生成した関数 add1 は第 2 引数の値を +1 します。

fold_right の場合、関数の第 2 引数が累積変数になるので、const (+1) を渡せば、第 1 引数を無視して第 2 引数の値を +1 することができます。これで二分木の要素数を求めることができます。

あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト をお読みください。

●プログラムリスト

--
-- Tree.hs : 二分探索木
--
--           Copyright (C) 2013-2021 Makoto Hiroi
--

module Tree (
  Tree,
  emptyTree, singleton, insert, 
  search, searchMin, searchMax,
  delete, deleteMin, deleteMax,
  toList, fromList,
  fold_left, fold_right, isEmptyTree
) where

-- データ型の定義
data Tree a = Nil | Node a (Tree a) (Tree a) deriving Show

-- 空の木
emptyTree :: Tree a
emptyTree = Nil

-- 要素が一つの木
singleton :: a -> Tree a
singleton x = Node x Nil Nil

-- データの挿入
insert :: Ord a => a -> Tree a -> Tree a
insert x Nil = singleton x
insert x (Node y l r)
  | x == y    = Node x l r
  | x < y     = Node y (insert x l) r
  | otherwise = Node y l (insert x r)

-- データの探索
search :: Ord a => a -> Tree a -> Maybe a
search _ Nil = Nothing
search x (Node y l r)
  | x == y    = Just y
  | x < y     = search x l
  | otherwise = search x r

searchMin :: Tree a -> Maybe a
searchMin Nil = Nothing
searchMin (Node x Nil _) = Just x
searchMin (Node _ l   _) = searchMin l

searchMax :: Tree a -> Maybe a
searchMax Nil = Nothing
searchMax (Node x _ Nil) = Just x
searchMax (Node _ _ r)   = searchMax r

-- データの削除
deleteMin :: Tree a -> Tree a
deleteMin Nil = Nil
deleteMin (Node _ Nil r) = r
deleteMin (Node x l   r) = Node x (deleteMin l) r

deleteMax :: Tree a -> Tree a
deleteMax Nil = Nil
deleteMax (Node _ l Nil) = l
deleteMax (Node x l r)   = Node x l (deleteMax r)

delete :: Ord a => a -> Tree a -> Tree a
delete x Nil = Nil
delete x (Node y l r)
  | x < y     = Node y (delete x l) r
  | x > y     = Node y l (delete x r)
  | otherwise = delete' l r where
      delete' Nil r = r
      delete' l Nil = l
      delete' l r = Node x' l (deleteMin r)
        where Just x' = searchMin r

-- データの変換
fromList :: Ord a => [a] -> Tree a
fromList xs = foldl (flip insert) Nil xs

toList :: Tree a -> [a]
toList tree = iter tree [] where
  iter Nil xs = xs
  iter (Node x l r) xs = iter l (x : iter r xs)

-- 畳み込み
fold_left :: (a -> b -> a) -> a -> Tree b -> a
fold_left _ a Nil = a
fold_left f a (Node x l r) = fold_left f (f (fold_left f a l) x) r

fold_right :: (a -> b -> b) -> b -> Tree a -> b
fold_right _ a Nil = a
fold_right f a (Node x l r) = fold_right f (f x (fold_right f a r)) l

-- 空の木か
isEmptyTree :: Tree a -> Bool
isEmptyTree Nil = True
isEmptyTree _   = False

マージソート

ソートのお話です。今まで例題としてクイックソートと挿入ソートを取り上げました。データ数を N とすると、挿入ソートの実行時間は N² に比例します。挿入ソートは遅いソートですが、クイックソートは高速なソートで、実行時間は N * log₂ N に比例します。

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

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

●リストのマージ

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

      図 : リストのマージ

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

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

リスト : リストのマージ

merge_list :: Ord a => [a] -> [a] -> [a]
merge_list [] ys = ys
merge_list xs [] = xs
merge_list a@(x:xs) b@(y:ys)
  | x <= y    = x : merge_list xs b
  | otherwise = y : merge_list a ys

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

リスト xs と ys にデータがあれば、先頭要素 x と y を演算子 <= で比較します。返り値が真であれば x を、そうでなければ y を merge_list が返すリストに追加します。merge_list を再帰呼び出しするとき、追加する要素をリストから取り除くことに注意してください。これでリストをマージすることができます。

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

*Main> merge_list [1,3,5,7,9] [2,4,6,8,10]
[1,2,3,4,5,6,7,8,9,10]
*Main> merge_list [1,3,5,7,9] []
[1,3,5,7,9]
*Main> merge_list [] [1,3,5,7,9]
[1,3,5,7,9]
*Main> merge_list [1,3,5,7,9] [2,4,6]
[1,2,3,4,5,6,7,9]
*Main> merge_list [1,3,5] [2,4,6,8,10]
[1,2,3,4,5,6,8,10]

●マージソートの実装

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

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

リスト : マージソート

merge_sort :: Ord a => Int -> [a] -> [a]
merge_sort _ []      = []
merge_sort 1 (x:_)   = [x]
merge_sort 2 (x:y:_) = if x > y then [y, x] else [x, y]
merge_sort n xs      =
  merge_list (merge_sort m xs) (merge_sort (n - m) (drop m xs))
    where m = div n 2

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

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

drop :: Int -> [a] -> [a]

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

Prelude> drop 3 [1,2,3,4,5]
[4,5]
Prelude> drop 0 [1,2,3,4,5]
[1,2,3,4,5]
Prelude> drop 5 [1,2,3,4,5]
[]

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

●実行例

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

*Main> merge_sort 10 [5,6,4,7,3,8,2,9,1,0]
[0,1,2,3,4,5,6,7,8,9]
*Main> merge_sort 10 [9,8,7,6,5,4,3,2,1,0]
[0,1,2,3,4,5,6,7,8,9]
*Main> merge_sort 10 [0,1,2,3,4,5,6,7,8,9]
[0,1,2,3,4,5,6,7,8,9]

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

●別解

リストを二分割していくのではなく、要素が 1 つのリストを作って、それを順番にマージしていくこともできます。次のリストを見てください。

リスト : マージソート (別解)

merge_sort' :: Ord a => [a] -> [a]
merge_sort' xs = iter1 (map (:[]) xs)
  where
    iter1 [x] = x
    iter1 xs = iter1 (iter2 xs)
    iter2 [] = []
    iter2 [x] = [x]
    iter2 (x:y:zs) = merge_list x y : iter2 zs

実際の処理は局所関数 iter1 と iter2 で行います。最初に、map で要素をリストに格納して、それを iter1 に渡します。iter1 はリストの要素がひとつになるまで、iter2 を繰り返し呼び出します。iter2 は先頭から順番にリストを 2 つ取り出して、それを merge_list でマージします。そして、その結果をリストに格納して返します。

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

*Main> merge_sort' [5,6,4,7,3,8,2,9,1,0]
[0,1,2,3,4,5,6,7,8,9]
*Main> merge_sort' [0..9]
[0,1,2,3,4,5,6,7,8,9]
*Main> merge_sort' [9,8..0]
[0,1,2,3,4,5,6,7,8,9]