M.Hiroi's Home Page

F# Programming

お気楽 F# プログラミング超入門

[ PrevPage | F# | NextPage ]

パターンマッチング

F# は「パターンマッチング (pattern matching)」を使って条件分岐を行うことができます。また、リストもパターンマッチングで分解することができます。これらの機能は論理型言語 Prolog のパターンマッチングと大変よく似ています。パターンマッチングは ML の特徴の一つで、とても便利な機能です。

●match 式

パターンマッチングは match 式で行います。match 式の構文を示します。

match 式0 with
  pattern_1 -> 式1
| pattern_2 -> 式2
  ...
| pattern_n -> 式n

| で区切られた部分をマッチング節 (matching clause) といいます。match 式は式 0 の評価結果とパターンを照合し、マッチングする節を選択して実行します。たとえば、式 0 の結果と pattern_1 がマッチングした場合、式 1 を評価してその結果が match 式の返り値になります。マッチングしない場合は次のパターンを調べます。マッチングするパターンが見つからない場合はエラーになります。

なお、一度マッチング節が選択された場合、それ以降の節は選択されません。また、式 1 から式 n の結果は同じ型でなければいけません。ご注意ください。

簡単な例を示しましょう。match 式を使って階乗を求める関数 fact を定義すると次のようになります。

リスト 1 : 階乗

// パターンマッチング未使用
let rec fact n =
  if n = 0 then 1
  else n * fact (n - 1)

// パターンマッチング
let rec fact n =
  match n with
    0 -> 1
  | n' -> n' * fact (n' - 1)

パターンが定数の場合、同じ値の引数とマッチングします。最初の定義はパターンが 0 なので、引数が 0 の場合にマッチングします。これは if n = 0 then 1 と同じ処理です。パターンが変数の場合はどんな値とでもマッチングします。そして、変数はその値に束縛されます。したがって、n が 0 以外の場合は 2 番目のパターンと一致し、変数 n' の値は n になります。ここで再帰呼び出しが行われます。

変数 n' は n と同じ値なので、パターンにワイルドカードを使って次のように定義してもかまいません。

| _ -> n * fact (n - 1)

このように、if を使わなくてもパターンマッチングでプログラムを作ることができます。

パターンマッチングを使うときは、マッチング節を定義する順番に気をつけてください。fact の場合、最初にパターン n' を定義すると、引数が 0 の場合でもマッチングするので、パターン 0 のマッチング節が実行されることはありません。特定のパターンから定義するように注意してください。

●function 文

match 式によるパターンマッチングは function 文を使うと簡単になります。function 文はラムダ式と match 式を組み合わせたものです。

function                    fun 引数 -> match 引数 with
  pattern_1 -> 式1           pattern_1 -> 式1
| pattern_2 -> 式2         | pattern_2 -> 式2
  ...                        ...
| pattern_n -> 式n         | pattern_n -> 式n

関数 fact を function 文で書き直すと次のようになります。

リスト 2 : 階乗 (2)

let rec fact = function
  0 -> 1
| n -> n * fact (n - 1)

カリー化関数で function 文を使うとき、一番最後の引数がマッチングの対象になることに注意してください。たとえば、2 つの整数の最大公約数を求める関数 gcd は次のようになります。

リスト 3 : 最大公約数

let rec gcd a = function
  0 -> a
| b -> gcd b (a % b)

●リストのパターンマッチング

リストの操作は関数 head, tail でリストを分解するよりも「パターンマッチング」を使った方が簡単です。リストもパターンとマッチングすることができます。リストのパターンはコンス演算子 :: を使って表します。たとえば、パターンを使って関数 append を定義すると次のようになります。

リスト 4 : リストの連結

let rec append xs ys = 
  match xs with
    [] -> ys
  | x :: xs -> x :: (append xs ys)

最初のパターンは、xs が [ ] とマッチングします。次の x :: xs がパターンを表します。このパターンはリストとマッチングして、先頭の要素が x に、先頭要素を取り除いた残りのリストが xs に束縛されます。このように、関数 head や tail を使わなくてもリストを分解することができます。

リストを表すパターンは x::xs だけではありません。よく使われるパターンを次に示します。

(1) [x]         要素が 1 つのリストとマッチング
(2) [x; y]      要素が 2 つのリストとマッチング
(3) x::xs       要素が 1 つ以上あるリストとマッチング
(4) x1::x2::xs  要素が 2 つ以上あるリストとマッチング
(5) x1::x1::xs  エラー

(5) のように、パターンの中に同名の変数を使うことはできません。この場合、x1::x2::xs とマッチングさせてから x1 と x2 が等しいかチェックします。このような場合、キーワード when を使うと便利です。when の構文を示します。

パターン when 条件式 -> 式

このようなマッチング節を「ガード付き節」といいます。パターンとの照合に成功して、かつ when の条件式が真を返す場合に限り式が評価されます。たとえば、when を使って (5) を実現すると次のようになります。

| x1::x2::xs when x1 = x2 -> 式1
| x1::x2::xs when x1 < x2 -> 式2
| x1::x2::xs -> 式3

パターンとの照合に成功して、x1 = x2 の場合は式 1 が評価されます。x1 < x2 の場合は式 2 が評価され、それ以外の場合は式 3 が評価されます。

また、もっと複雑なリストもパターンで表すことができます。

(1) (x, y)::xs  要素が組のリストとマッチング
    ex) [(1, 2); (3, 4); (5, 6)] => x = 1, y = 2, xs = [(3, 4); (5, 6)]

(2) (x::xs)::ys 要素がリストのリスト ('a list list) とマッチング
    ex) [[1; 2; 3], [4; 5], [6]] => x = 1, xs = [2; 3], ys = [[4; 5]; [6]]

ご参考までに、関数 length, reverse, member をパターンマッチングを使って書き直してみましょう。

リスト 5 : パターンマッチングの使用例

// リストの長さ
let rec length = function
  [] -> 0
| x :: xs -> 1 + length xs

// リストの反転
let rec reverse = function
  [] -> []
| x :: xs -> reverse xs @ [x]

// 探索
let rec mem x = function
  [] -> []
| (y :: ys) as xs when x = y -> xs
| (y :: ys) -> mem x ys

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

パターン as 変数名

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

xs => [1; 2; 3]
y  => 1
ys => [2; 3]

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

●問題

次の関数をパターンマッチングを使って書き直してください。

  1. 要素 x を n 個持つリストを生成する関数 make_list x n
  2. リスト xs の先頭から n 個の要素を取り出す関数 take xs n
  3. リストの先頭から n 個の要素を取り除く関数 drop xs n
  4. 2 つのリスト xs, ys の要素をタプルにまとめたリストを返す関数 zip xs ys
  5. zip の逆変換を行う関数 unzip












●解答

リスト : パターンマッチングの使用例

let rec make_list x n =
  match n with
    0 -> []
  | n -> x :: make_list x (n - 1)

let rec take xs n =
  match (n, xs) with
    (0, _) | (_, []) -> []
  | (_, y::ys) -> y :: take ys (n - 1)

let rec drop xs n =
  match (n, xs) with
    (0, _) -> xs
  | (_, []) -> []
  | (_, _::ys) -> drop ys (n - 1)

let rec zip xs ys =
  match (xs, ys) with
    ([], _) | (_, []) -> []
    | (x::xs1, y::ys1) -> (x, y) :: zip xs1 ys1

let rec unzip = function
    [] -> ([], [])
  | (x, y)::zs -> let (xs, ys) = unzip zs in (x::xs, y::ys)

高階関数 (2)

関数型言語の場合、リスト操作関数の多くは高階関数として定義されています。今回はよく使われる高階関数として、マッピング、フィルター、畳み込み (縮約) について説明します。

●マッピング

まず最初に、リストの要素に関数 f を適用して、その結果をリストに格納して返す関数を作ってみましょう。このような操作を「マッピング (写像)」といいます。次のリストを見てください。

リスト 6 : マッピング

let rec mapcar f = function
  [] -> []
| x :: xs -> f x :: mapcar f xs

関数名は mapcar としました。名前は Common Lisp から拝借しました。なお、F# には同じ機能を持つ関数 List.map があります。

プログラムは簡単です。パターンマッチングで引数のリストを先頭の要素 x と残りのリスト xs に分解します。そして、x に関数 f を適用した結果と mapcar f xs の結果をコンス演算子 :: で結合します。引数のリストが空リストの場合が再帰呼び出しの停止条件になります。

mapcar を定義すると、次のように表示されます。

val mapcar: f: ('a -> 'b) -> _arg1: 'a list -> 'b list

第 1 引数が関数型 'a -> 'b で第 2 引数がリスト 'a list になります。関数 f はリストの要素を受け取るので、関数 f の引数の型とリストの型は一致します。これを型変数 'a で表しています。同様に、関数 f の返り値の型と mapcar の返り値のリストの型は一致します。これを型変数 'b で表しています。このように、mapcar は多相型関数として定義されます。

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

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

●フィルター

フィルター (filter) はリストの要素に関数を適用し、関数が真を返す要素をリストに格納して返す関数です。真または偽を返す関数のことを「述語 (predicate)」といいます。ここでは簡単な例題として、述語が真を返す要素を削除する関数 remove_if を作ってみましょう。名前は Common Lisp から拝借しました。

リスト 7 : 要素の削除

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

mapcar と同様に remove_if も簡単です。f x が真ならば x をリストに加えません。偽ならば x をリストに加えるだけです。remove_if を定義すると次のようになります。

val remove_if: f: ('a -> bool) -> _arg1: 'a list -> 'a list

関数 f が if の条件式で使われているので、F# は関数 f の型を 'a -> bool と推論しています。もちろん、remove_if も多相型関数として定義されます。F# の型推論はとても便利ですね。簡単な実行例を示します。

> remove_if (fun x -> x % 2 = 0) [1; 2; 3; 4; 5];;
val it: int list = [1; 3; 5]

> remove_if (fun x -> x = "abc") ["abc"; "def"; "abc"; "ghi"];;
val it: string list = ["def"; "ghi"]

最初の例では偶数の要素が削除されます。次の例は文字列 "abc" が削除されます。

もちろん、フィルターも簡単に定義することができます。remove_if とは逆に、述語が真を返すとき要素をリストに追加し、偽を返すときはリストに加えません。なお、F# には同様の動作を行う関数 List.filter があります。

リスト 8 : フィルター

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

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

> filter (fun x -> x % 2 = 0) [1;2;3;4;5];;
val it: int list = [2; 4]

●畳み込み

2 つの引数を取る関数 f とリストを引数に受け取る関数 reduce を考えます。reduce はリストの各要素に対して関数 f を図 1 のように適用します。

(1) [a1; a2; a3; a4; a5]
    => f( f( f( f( a1, a2 ), a3 ), a4 ), a5 )

(2) [a1; a2; a3; a4; a5]
    => f( a1, f( a2, f( a3, f( a4, a5 ) ) ) )


        図 1 : 関数 reduce の動作

関数 f を適用する順番で 2 通りの方法があります。図 1 (1) はリストの先頭から f を適用し、図 1 (2) はリストの後ろから f を適用します。たとえば、関数 f が単純な加算関数とすると、reduce の結果はどちらの場合もリストの要素の和になります。

f(x, y) = x + y の場合
reduce => a1 + a2 + a3 + a4 + a5

このように、reduce はリストのすべての要素を関数 f を用いて結合します。このような操作を「縮約」とか「畳み込み」といいます。また、reduce の引数に初期値 g を指定することがあります。この場合、reduce は図 2 に示す動作になります。

(1) [a1; a2; a3; a4; a5]
    => f( f( f( f( f( g, a1 ), a2 ), a3 ), a4 ), a5 )

(2) [a1; a2; a3; a4; a5]
    => f( a1, f( a2, f( a3, f( a4, f( a5, g ) ) ) ) )


        図 2 : reduce() の動作 (2)

ここでは簡単な例題として、図 2 (1) の動作を行う関数 reduce と、図 2 (2) の動作を行う関数 reduce_right を作ってみましょう。なお、F# には同様の動作を行う関数 List.fold と List.foldBack があります。

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

リスト 9 : 畳み込み

let rec reduce f a = function
  [] -> a
| x :: xs -> reduce f (f a x) xs

let rec reduce_right f a = function
  [] -> a
| x :: xs -> f x (reduce_right f a xs)

第 1 引数 f が適用する関数、第 2 引数 a が初期値、第 3 引数がリストです。最初のマッチング節は再帰呼び出しの停止条件ですが、reduce (reduce_right) に空リストが与えられた場合にも対応します。この場合は初期値 a を返します。次のマッチング節でリストの要素を取り出して関数 f を呼び出します。

たとえば、リストが [1; 2; 3] で a が 0 とします。最初は f(0, 1) が実行され、その返り値が reduce の第 2 引数に渡されます。次は f(a, 2) が実行されますが、これは f(f(0, 1), 2) と同じことです。そして、その結果が reduce の第 2 引数になります。最後に f(a, 3) が実行されますが、これは f(f(f(0, 1), 2), 3) となり、図 2 (1) と同じ動作になります。

reduce の場合、リストの要素が関数 f の第 2 引数になり、第 1 引数にはこれまでの処理結果が渡されます。これに対し、reduce_right の場合は逆になり、関数 f の第 1 引数にリストの要素が渡されて、これまでの処理結果は第 2 引数に渡されます。これで図 2 (2) の動作を実現することができます。

それでは、reduce と reduce_right の型を示します。

val reduce: f: ('a -> 'b -> 'a) -> a: 'a -> _arg1: 'b list -> 'a
val reduce_right: f: ('a -> 'b -> 'b) -> a: 'b -> _arg1: 'a list -> 'b

reduce と reduce_right の返り値は初期値 a の型と同じになります。つまり、リストの要素と同じ型である必要はありません。そして、渡される関数の型にも注目してください。reduce の場合、関数の第 1 引数と初期値の型が同じです。第 1 引数に今までの処理結果が渡されて、第 2 引数にリストの要素が渡されることがわかります。これに対し、reduce_right は逆になっていることに注意してください。

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

> reduce (fun x y -> x + y) 0 [1; 2; 3; 4; 5];;
val it: int = 15

> reduce_right (fun x y -> x + y) 0 [1; 2; 3; 4; 5];;
val it: int = 15

●畳み込みの使用例

ところで、reduce, reduce_right と 2 引数の関数を組み合わせると、いろいろな関数を実現することができます。最初に length の例を示します。

> reduce (fun x y -> x + 1) 0 [0; 1; 2; 3; 4; 5];;
val it: int = 6

> reduce_right (fun x y -> y + 1) 0 [0; 1; 2; 3; 4; 5];;
val it: int = 6

reduce で length を実現する場合、初期値を 0 にして第 1 引数の値を +1 することで実現できます。reduce_right の場合は第 2 引数の値を +1 します。

次に map の例を示します。

> reduce_right (fun x y -> (x * x)::y) [] [1; 2; 3; 4; 5];;
val it: int list = [1; 4; 9; 16; 25]

map の場合は reduce_rigth を使うと簡単です。初期値を [ ] にして第 1 引数の計算結果を第 2 引数のリストに追加するだけです。

次に filter の例を示します。

> reduce_right (fun x y -> if x % 2 = 0 then x::y else y) [] [1; 2; 3; 4; 5];;
val it: int list = [2; 4]

filter の場合も初期値を [ ] にして、第 1 引数が条件を満たしていれば第 2 引数のリストに追加します。

最後に述語が真となる要素の個数を求めてみましょう。これは Common Lisp の関数 count-if と同じです。

> reduce (fun x y -> if y % 2 = 0 then x + 1 else x) 0 [1; 2; 3; 4; 5];;
val it: int = 2

このように、畳み込みを使っていろいろな処理を実現することができます。

●問題

次に示す高階関数を定義していください。

  1. s から e までの整数に関数 fn を適用し、その結果をリストに格納して返す関数 tabulate fn s e
  2. リスト xs の要素に関数 fn を適用するが、その結果を累積しない関数 foreach fn xs
  3. 関数 fn にリストを渡すマップ関数 maplist fn xs
  4. 述語 pred を満たす要素を先頭から取り出す関数 take_while pred xs
  5. 述語 pred を満たす要素を先頭から取り除く関数 drop_while pred xs
  6. リスト xs を先頭から畳み込むとき、計算途中の累積値をリストに格納して返す scan_left fn a xs
  7. リスト xs を末尾から畳み込むとき、計算途中の累積値をリストに格納して返す scan_right fn a xs












●解答

リスト : 解答例

let rec tabulate fn s e =
  if s > e then []
  else fn s :: tabulate fn (s + 1) e

let rec foreach fn = function
    [] -> ()
  | x::xs -> begin fn x; foreach fn xs end

let rec maplist fn = function
    [] -> []
  | _::ys as xs -> fn xs :: maplist fn ys

let rec take_while pred = function
    x::xs when pred x -> x :: take_while pred xs
  | _ -> []

let rec drop_while pred = function
    x::xs when pred x -> drop_while pred xs
  | xs -> xs

let rec scan_left fn a = function
    [] -> [a]
  | x::xs -> a :: scan_left fn (fn a x) xs

let rec scan_right fn a = function
    [] -> [a]
  | x::xs -> let ys = scan_right fn a xs in fn x (List.head ys) :: ys
val tabulate: fn: (int -> 'a) -> s: int -> e: int -> 'a list
val foreach: fn: ('a -> unit) -> _arg1: 'a list -> unit
val maplist: fn: ('a list -> 'b) -> _arg1: 'a list -> 'b list
val take_while: pred: ('a -> bool) -> _arg1: 'a list -> 'a list
val drop_while: pred: ('a -> bool) -> _arg1: 'a list -> 'a list
val scan_left: fn: ('a -> 'b -> 'a) -> a: 'a -> _arg1: 'b list -> 'a list
val scan_right: fn: ('a -> 'b -> 'b) -> a: 'b -> _arg1: 'a list -> 'b list
> tabulate (fun x -> x) 1 10;;
val it: int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

> tabulate (fun x -> x * x) 1 10;;
val it: int list = [1; 4; 9; 16; 25; 36; 49; 64; 81; 100]

> tabulate (fun x -> x * x * x) 1 10;;
val it: int list = [1; 8; 27; 64; 125; 216; 343; 512; 729; 1000]

> foreach (fun x -> printfn "%d" x) [1;2;3;4;5];;
1
2
3
4
5
val it: unit = ()

> maplist (fun x -> x) [1; 2; 3; 4; 5];;
val it: int list list =
  [[1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; 5]; [4; 5]; [5]]

> maplist List.length [1; 2; 3; 4; 5];;
val it: int list = [5; 4; 3; 2; 1]

> take_while (fun x -> x % 2 = 0) [2; 4; 6; 8; 1; 3; 5; 7];;
val it: int list = [2; 4; 6; 8]

> take_while (fun x -> x % 2 = 0) [1; 3; 5; 7];;
val it: int list = []

> take_while (fun x -> x % 2 = 1) [1; 3; 5; 7];;
val it: int list = [1; 3; 5; 7]

> drop_while (fun x -> x % 2 = 0) [2; 4; 6; 8; 1; 3; 5; 7];;
val it: int list = [1; 3; 5; 7]

> drop_while (fun x -> x % 2 = 0) [1; 3; 5; 7];;
val it: int list = [1; 3; 5; 7]

> drop_while (fun x -> x % 2 = 1) [1; 3; 5; 7];;
val it: int list = []

> scan_left (fun x y -> x + y) 0 [1;2;3;4;5;6;7;8;9;10];;
val it: int list = [0; 1; 3; 6; 10; 15; 21; 28; 36; 45; 55]

> scan_left (fun x y -> x * y) 1 [1;2;3;4;5;6;7;8;9;10];;
val it: int list = [1; 1; 2; 6; 24; 120; 720; 5040; 40320; 362880; 3628800]

> scan_left (fun x y -> y::x) [] [1;2;3;4;5];;
val it: int list list =
  [[]; [1]; [2; 1]; [3; 2; 1]; [4; 3; 2; 1]; [5; 4; 3; 2; 1]]

> scan_right (fun x y -> x + y) 0 [1;2;3;4;5;6;7;8;9;10];;
val it: int list = [55; 54; 52; 49; 45; 40; 34; 27; 19; 10; 0]

> scan_right (fun x y -> x::y) [] [1;2;3;4;5];;
val it: int list list =
  [[1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; 5]; [4; 5]; [5]; []]

scan_left はリストの最後の要素が最終の累積値になります。xs が空リストのとき、累積変数 a の値をリストに格納して返します。そうでなければ、scan_left を再帰呼び出しして、その返り値に累積変数 a の値を追加して返します。scan_left を再帰呼び出しするときは、関数 fn を呼び出して累積変数の値を更新することに注意してください。

scan_right はリストの先頭の要素が最終の累積値、最後の要素が初期値になります。リスト xs が空リストの場合は [a] を返します。そうでなければ、scan_right を再帰呼び出しします。このとき、累積変数 a の値は更新しません。返り値のリストは変数 ys にセットします。この ys の先頭要素が一つ前の累積値になるので、この値とリストの先頭要素 x を関数 fn に渡して評価します。あとは、fn の返り値を ys の先頭に追加して返せばいいわけです。


ソート

ソート (sort) はある規則に従ってデータを順番に並べ換える操作のことです。たとえば、データが整数であれば大きい順に並べる、もしくは小さい順に並べます。 F# にはリストをソートする関数 List.sort がありますが、私達でも簡単に作ることができます。

今回は挿入ソート (insert sort) とクイックソート (quick sort) を取り上げます。

●挿入ソート

挿入ソートの考え方はとても簡単です。ソート済みのリストに新しいデータを挿入していくことでソートを行います。たとえば、リスト [2; 4; 6] に 5 を挿入する場合、リストの要素 n と 5 を順番に比較して、5 < n を満たす位置に 5 を挿入すればいいわけです。この場合は、4 と 6 の間に 5 を挿入すればいいですね。

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

リスト 10 : 挿入ソート

let rec insert_sort xs =
  let rec insert_element x = function
    [] -> [x]
  | (y::ys) as a -> if x < y then x::a else y::insert_element x ys
  in
    match xs with
      [] -> []
    | y::ys -> insert_element y (insert_sort ys)

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

局所関数 insert_element は再帰呼び出しでリストをたどり、データ x を挿入する位置を探します。引数のリストが空リストであれば、x が一番大きなデータです。リスト [x] を返します。これで、リストの最後尾に x を挿入することができます。次の節でリストを分解して、x が先頭の要素 y よりも小さい場合は、その位置に x を挿入します。そうでなければ、insert_element を再帰呼び出しします。

insert_sort の型は次のようになります。

val insert_sort: xs: 'a list -> 'a list when 'a: comparison

comparison は「比較制約」といって、型 'a は比較がサポートされている必要があります。

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

> insert_sort [9; 1; 8; 2; 7; 3; 6; 4; 5];;
val it: int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
# insert_sort [9; 1; 8; 2; 7; 3; 6; 4; 5];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

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

●クイックソート

ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。その中でも「クイックソート (quick sort)」は高速なアルゴリズムとして有名です。

クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。基準になる値のことを「枢軸 (pivot)」といいます。枢軸は要素の中から適当な値を選んでいいのですが、リストの場合は任意の要素を簡単に選ぶことができません。この場合、いちばん簡単に求めることができる先頭の要素を枢軸とします。

リストを 2 つに分けたら、それらを同様にソートします。これは、再帰を使えば簡単に実現できます。その結果を枢軸を挟んで結合します。これを図に表すと次のようになります。

    [5; 3; 7; 6; 9; 8; 1; 2; 4]

          5 を枢軸に分割

   [3; 1; 2; 4]  5  [7; 6; 9; 8]

   3を枢軸に分割    7を枢軸に分割

 [1; 2]  3  [4] | 5 | [6]  7  [9; 8]

  ・・・分割を繰り返していく・・・    


        図 3 : クイックソート

このようにリストを分割していくと、最後は空リストになります。ここが再帰の停止条件になります。あとは分割したリストを結合していけばいいわけです。プログラムは次のようになります。

リスト 11 : クイックソート

let rec quick_sort = function
  [] -> []
| x::xs ->
    let (m, n) = partition x xs in
    quick_sort m @ (x :: quick_sort n)

最初の節が空リストの場合で、再帰呼び出しの停止条件になります。次の節でリストを分割してソートを行います。パターン x::xs でリストを分解し、リストの先頭要素 x を枢軸とします。

リストの分割は関数 partition で行います。partition は x を基準にリストを 2 つに分割し、それらのリストを組 (a, b) で返します。リスト a が枢軸よりも小さな要素を集めたもので、リスト b が枢軸以上の要素を集めたものです。なお、F# には同様の処理を行う関数 List.partition があります。List.partition は高階関数です。

quick_sort では let で局所変数 m と n を定義し、partition を呼び出して返り値をパターンで受け取ります。そして、quick_sort を再帰呼び出しして、リスト m, n をソートします。あとは、その結果を枢軸 x を挟んで結合すればいいわけです。

次はリストを分割する関数 partition を説明します。

リスト 12 : リストの分割

let rec partition n = function
  [] -> ([], [])
| x::xs -> let (a, b) = partition n xs in
           if x < n then (x::a, b) else (a, x::b)

最初の節が空リストの場合です。これが再帰呼び出しの停止条件になります。空リストの場合は 組 ([], []) を返します。次の節でリストを分割します。引数のリストをパターン x::xs で分解し、partition を再帰呼び出ししてリスト xs を 2 つに分割します。返り値は局所変数 (a, b) で受け取ります。

あとは、枢軸 n と要素 x を比較して、x が n よりも小さければ x をリスト a に追加して返します。そうでなければ、x をリスト b に追加して返します。これで枢軸 n を基準にしてリストを 2 分割することができます。

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

val partition: n: 'a -> _arg1: 'a list -> 'a list * 'a list when 'a: comparison
val quick_sort: _arg1: 'a list -> 'a list when 'a: comparison
> quick_sort [5; 3; 7; 6; 9; 8; 1; 2; 4];;
val it: int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

正常に動作していますね。なお、partition は次のように末尾再帰でプログラムすることもできます。

リスト 13 : クイックソート

// リストの分割 (末尾再帰)
let rec partition n a b = function
  [] -> (a, b)
| x::xs -> if x < n then partition n (x::a) b xs
              else partition n a (x::b) xs

let rec quick_sort = function
  [] -> []
| x::xs ->
    let (m, n) = partition x [] [] xs in
    quick_sort m @ (x :: quick_sort n)

●クイックソートの弱点

クイックソートの実行時間は、データ数を N とすると平均して N * log2 N に比例します。ところが、枢軸の選び方によっては、最悪で N の 2 乗に比例するところまで劣化します。つまり、挿入ソートと同じくらい遅くなってしまうのです。たとえば、リストの先頭要素を枢軸として選ぶ場合、リストの要素が昇順または降順に並んでいると最悪の結果になります。

このため、クイックソートをプログラムする場合、枢軸の選び方を工夫するのが一般的です。たとえば、データの中からいくつかの要素を選び、その中で中間の値を持つ要素を枢軸に選びます。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は減少しますが、中間の値を選ぶのに時間がかかってしまいます。実際には、3 つから 5 つの要素を選んで、その中で中間の値を枢軸とする場合が多いようです。

ただし、この改良方法はリストには不向きであることに注意してください。リストはデータ数が多くなるほど、後ろのデータを取り出すのに時間がかかるようになります。先頭から 3 つのデータを取り出して枢軸を選んだとしても、降順または昇順に並んだデータには効果が無いのは明らかです。このため、リストのソートはクイックソートよりも「マージソート (merge sort)」の方が適しているといわれています。マージソートについては、あとで取り上げる予定です。

●問題

  1. 述語 pred でリスト xs を二分割する関数 parititon_if pred xs を定義してください
  2. partition_if を使って quick_sort を定義してください












●解答

リスト : リストの分割とクイックソート

let rec partition_if pred = function
    [] -> ([], [])
  | x::xs -> let (ys, zs) = partition_if pred xs in
             if pred x then (x::ys, zs) else (ys, x::zs)

let rec quick_sort = function
  [] -> []
| x::xs ->
    let (ys, zs) = partition_if (fun y -> y < x) xs in
    quick_sort ys @ (x :: quick_sort zs)
val partition_if: pred: ('a -> bool) -> _arg1: 'a list -> 'a list * 'a list
val quick_sort: _arg1: 'a list -> 'a list when 'a: comparison
> partition_if (fun x -> x % 2 = 0) [1;2;3;4;5;6;7;8;9;10];;
val it: int list * int list = ([2; 4; 6; 8; 10], [1; 3; 5; 7; 9])

> quick_sort [5;3;7;4;6;8;2;9;1;0];;
val it: int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]

> quick_sort [0;1;2;3;4;5;6;7;8;9];;
val it: int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]

> quick_sort [9;8;7;6;5;4;3;2;1;0];;
val it: int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]

Copyright (C) 2022 Makoto Hiroi
All rights reserved.

[ PrevPage | F# | NextPage ]