関数を定義する場合、引数に「パターン (pattern)」を使うことができます。Haskell は ML 系統の言語なので、そのパターンマッチングは論理型言語 Prolog のそれとよく似ています。たとえば、パターンを使って階乗を求める関数 fact を定義すると次のようになります。
リスト : 階乗 fact :: Integer -> Integer fact n = if n == 0 then 1 else n * fact (n - 1) -- パターンを使う場合 fact' :: Integer -> Integer fact' 0 = 1 fact' n = n * fact' (n - 1)
Haskell で関数を定義する場合、同じ関数名で複数の定義 (節) を記述することができます。このとき、各節で記述した仮引数がパターンになります。Haskell は実引数とパターンを照合し、マッチングする節を選択して実行します。当然ですが、各節の返り値は同じデータ型でなければなりません。
パターンが定数の場合、同じ値の実引数とマッチングします。fact' の最初の定義はパターンが 0 なので、実引数が 0 の場合にマッチングします。これは if n == 0 then 1 と同じ処理です。パターンが変数の場合、どんな値とでもマッチングします。したがって、n が 0 以外の場合は 2 番目の節と一致します。ここで再帰呼び出しが行われます。このように、if を使わなくてもパターンマッチングでプログラムを作ることができます。
パターンを使うときは、関数を定義する順番に気をつけてください。fact' の場合、最初に fact' n を定義すると、実引数が 0 の場合でもマッチングするので、fact' 0 の節が選択されなくなります。引数を特定するパターンから定義するように注意してください。
もうひとつ、簡単な例題としてフィボナッチ関数 fibo をパターンを使って書き直してみましょう。次のリストを見てください。
リスト : フィボナッチ関数 fibo :: Integer -> Integer fibo n = if n == 0 || n == 1 then n else fibo (n - 1) + fibo (n - 2) -- パターンを使う場合 fibo' :: Integer -> Integer fibo' 0 = 0 fibo' 1 = 1 fibo' n = fibo' (n - 1) + fibo' (n - 2)
fibo' の最初の節は実引数が 0 のとき、2 番目の節は 1 のときに選択されます。それ以外の場合は最後の節が選択され、fibo を 2 回再帰呼び出しします。
実引数を定数ではなく範囲で場合分けしたいときは「ガード (guard)」を使うと便利です。ガードを使って fact を書き直すと次のようになります。
リスト : 階乗 fact :: Integer -> Integer fact n = if n == 0 then 1 else n * fact (n - 1) -- ガードを使う場合 fact' :: Integer -> Integer fact' n | n < 0 = error "fact' out of range" | n == 0 = 1 | otherwise = n * fact' (n - 1)
ガードは引数の後ろに複数の節を縦線 '|' で分けて記述します。縦線の後ろには条件式と記号 = が続き、その後ろに節の本体 (式) を定義します。ガードは各節の条件式を順番に評価し、真を返す節を選択します。そして、記号 = の右辺にある式を評価し、その結果が関数の返り値となります。当然ですが、各節の返り値は同じデータ型でなければなりません。
関数 fact' の最初の節は n が負の場合です。この場合、引数は範囲外の値なので関数 error でエラーを送出します。ここで詳しい説明はしませんが、error は引数の文字列を画面 (標準エラー出力) に表示して、プログラムの実行を中断する関数です。ghci の場合、プログラムの実行を中断してトップレベルに戻ります。
2 番目の節は n が 0 のときに選択され、返り値は 1 となります。3 番目の節の otherwise は True と同じ意味で、最後には必ずこの節が選択されます。ここで fact' が再帰呼び出しされます。
もうひとつ簡単な例題として、関数 fibo をガードを使って書き直してみましょう。
リスト : フィボナッチ関数 fibo :: Integer -> Integer fibo n = if n == 0 || n == 1 then 1 else fibo (n - 1) + fibo (n - 2) -- ガードを使う場合 fibo' :: Integer -> Integer fibo' n | n < 0 = error "fibo' out of range" | n < 2 = n | otherwise = fibo' (n - 1) + fibo' (n - 2)
関数 fibo' の最初の節は、n が負のときに選択されます。引数が範囲外の値なのでエラーを送出します。n が 0 または 1 の場合は 2 番目の節が選択され、返り値は n になります。それ以外の場合は最後の節が選択されて、fibo' を 2 回再帰呼び出しします。
パターンとガードは併用することができます。たとえば、関数 fact と fibo は次のように記述することができます。
リスト : パターンとガードの併用 -- 階乗 fact'' :: Integer -> Integer fact'' n | n < 0 = error "fact out of range" fact'' 0 = 1 fact'' n = n * fact' (n - 1) -- フィボナッチ関数 fibo'' :: Integer -> Integer fibo'' n | n < 0 = error "fibo out of range" fibo'' 0 = 0 fibo'' 1 = 1 fibo'' n = fibo'' (n - 1) + fibo'' (n - 2)
fact'' の最初の節にガードが設定されています。n が負の場合はエラーを送出し、それ以外の場合は条件を満たすガード節がないので、次の節 fact'' 0 と実引数を照合します。最初の節のガード節に otherwise を追加すると、それ以降の節が選択されなくなります。ご注意ください。関数 fibo'' の場合も同様です。
リストもパターンとマッチングすることができます。リストのパターンはコンス演算子 : を使って表します。たとえば、パターンを使って関数 append を定義すると次のようになります。
リスト：リストの連結 append :: ([a], [a]) -> [a] append (xs, ys) = if null xs then ys else head xs : append (tail xs, ys) -- パターンを使う場合 append' :: ([a], [a]) -> [a] append' ([], ys) = ys append' (x:xs, ys) = x : append' (xs, ys)
append' の最初の節を見てください。タプルの第 1 要素は空リスト [ ] とマッチングします。次の節の x : xs がパターンを表します。このパターンはリストとマッチングして、先頭の要素が変数 x に、先頭要素を取り除いた残りのリストが変数 xs に束縛されます。このように、関数 head や tail を使わなくてもリストを分解することができます。
簡単な例として、前回作成した関数 length', reverse', member をパターンを使って書き直してみます。
リスト : パターンを使ったリスト操作 -- リストの長さ length' :: [a] -> Int length' xs = if null xs then 0 else 1 + length (tail xs) -- パターンを使う場合 length'' :: [a] -> Int length'' [] = 0 length'' (x:xs) = 1 + length xs -- リストの反転 reverse' :: [a] -> [a] reverse' xs = if null xs then [] else reverse' (tail xs) ++ [head xs] -- パターンを使う場合 reverse'' :: [a] -> [a] reverse'' [] = [] reverse'' (x:xs) = reverse'' xs ++ [x] -- リストの探索 member :: Eq a => (a, [a]) -> [a] member (x, xs) = if null xs then [] else if x == head xs then xs else member (x, tail xs) -- パターンを使う場合 member' :: Eq a => (a, [a]) -> [a] member' (_, []) = [] member' (x, xs@(y:ys)) | x == y = xs | otherwise = member' (x, ys)
ここで、member' の最初の節を見てください。引数のアンダーライン ( _ ) は「匿名変数 (anonymous variable)」を表します。匿名変数はどの値ともマッチングするワイルドカードとして機能します。ただし、マッチングした値を参照することはできません。値を必要としない引数は匿名変数を使うと便利です。
第 2 節で、パターン y : ys を使ってリストを分解しますが、分解した値 y や ys だけではなく、元のリストの値を参照したいときがあります。このような場合、記号 @ を使うと変数とパターンを同時に設定することができます。これを「as パターン」といいます。
変数名 @ パターン
たとえば、xs@(y : ys) と [1, 2, 3] をマッチングさせると、次のようになります。
xs => [1, 2, 3] y => 1 ys => [2, 3]
このように、パターン xs@(y : ys) とマッチングした場合、変数 xs の値は分解する前の [1, 2, 3] になります。
ところで、リストを表すパターンは 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 とマッチングさせてから if またはガードで x1 と x2 が等しいかチェックすることになります。また、もっと複雑なリストもパターンで表すことができます。
(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]] とマッチング
ex) [[1, 2, 3], [4, 5], [6]] => x = 1, xs = [2, 3], ys = [[4, 5], [6]]
このように、パターンはとても強力な機能です。Haskell は型チェックを厳密に行う関数型言語ですが、型推論、多相型関数、パターンなどの機能により、とても柔軟にプログラミングすることができます。
パターンは Common Lisp の cond や case のような条件分岐にも使うことができます。Haskell には case 式が用意されています。
case expr of pat1 -> expr1
pat2 -> expr2
.....
patN -> exprN
of のあとはレイアウトを使用することができます。pat はパターン (pattern) のことです。最初に case は式 expr を評価します。その結果とマッチングするパターンの節を選択し、対応する式を評価します。そして、その結果が case 式の返り値となります。
なお、一度節が選択されたら、それ以降の節は選択されません。それから、節の式 expr1, ..., exprN の返り値は同じデータ型でなければいけません。ご注意ください。
簡単な例を示します。関数 fact と fibo は case 式を使って次のように書くことができます。
リスト : case 式の例
-- 階乗
fact :: Integer -> Integer
fact n =
case n of
0 -> 1
_ -> n * fact (n - 1)
-- フィボナッチ関数
fibo :: Integer -> Integer
fibo n =
case n of
0 -> 1
1 -> 1
_ -> fibo (n - 1) + fibo (n - 2)
どちらの関数も最後の節は匿名変数を使っているので、どんな値でも最後の節で照合は成功します。
case 式の中でガードを使うこともできます。
リスト : case 式とガードの例
-- 階乗
fact' :: Integer -> Integer
fact' n =
case n of
0 -> 1
_ | n < 0 -> error "fact out of range"
| otherwise -> n * fact' (n - 1)
-- フィボナッチ関数
fibo' :: Integer -> Integer
fibo' n =
case n of
0 -> 1
1 -> 1
_ | n < 0 -> error "fibo out of range"
| otherwise -> fibo' (n - 1) + fibo' (n - 2)
case 式の中で階乗を使う場合、パターンの後ろで複数の節を縦線 ( | ) で区切ります。そのあと、"条件式 -> 式" を記述します。関数定義のガードと違って、記号は -> を使うことに注意してください。
case 式を使っていろいろな機能を実現することができます。たとえば、if-then-else は次のように case 式で表すことができます。
if E then F else G ==> case E of
Ture -> F
False -> G
パターンの定義は True と False しかありません。したがって、式 E が bool 以外のデータ型だとエラーになるわけです。
case 式のパターンには変数を使うことができます。変数は局所変数として扱われ、有効範囲は対応する規則の式の中だけになります。たとえば、リストの操作関数 length', append, reverse', member を case 式を使って書き直すと次のようになります。
リスト : リスト操作関数を case 式で書き換え
length' :: [a] -> Int
length' xs =
case xs of
[] -> 0
(_:ys) -> 1 + length ys
append :: ([a],[a]) -> [a]
append (xs, ys) =
case xs of
[] -> ys
(z:zs) -> z : append (zs, ys)
reverse' :: [a] -> [a]
reverse' xs =
case xs of
[] -> []
(y:ys) -> reverse' ys ++ [y]
member :: Eq a => (a, [a]) -> [a]
member (x, xs) =
case xs of
[] -> []
(y:ys) | x == y -> xs
| otherwise -> member (x, ys)
実際のところ、関数定義でパターンマッチングやガードが使えるので、case 式を使う機会はそれほど多くないと思います。
それでは、簡単な例題としてリストをソート (sort) するプログラムを作ってみましょう。ソートは、ある規則に従ってデータを順番に並べることです。たとえば、データが整数であれば、大きい順かもしくは小さい順に並べます。ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。
まずは簡単なソートアルゴリズムである「挿入ソート (insert sort)」を作ってみましょう。挿入ソートの考え方はとても簡単です。ソート済みのリストに新しいデータを挿入していくことでソートを行います。たとえば、リスト [2, 4, 6] に 5 を挿入する場合、リストの要素 n と 5 を順番に比較して、5 < n を満たす位置に 5 を挿入すればいいわけです。この場合は、4 と 6 の間に 5 を挿入すればいいですね。
ソートするリストは、tail で分解していくと空リストになります。これをソート済みのリストと考えて、ここにデータを挿入していきます。プログラムは次のようになります。
リスト : 挿入ソート insert_element :: Ord a => (a, [a]) -> [a] insert_element (x, []) = [x] insert_element (x, xs@(y:ys)) | x <= y = x:xs | otherwise = y : insert_element (x, ys) insert_sort :: Ord a => [a] -> [a] insert_sort [] = [] insert_sort (x:xs) = insert_element(x, insert_sort xs)
関数型の宣言で型クラス制約に Ord を指定しています。これは比較演算子を定義している型クラスです。Haskell の場合、基本的な型は Ord のインスタンスになっています。逆に言えば、型が Ord のインスタンスであれば、関数 insert_sort を適用することができます。
関数 insert_sort は引数のリストを再帰呼び出しで分解します。insert_sort を再帰呼び出ししてリスト ys をソートし、そのリストに先頭要素 y を関数 insert_element で挿入します。
関数 insert_element は再帰呼び出しでリストをたどり、データ x を挿入する位置を探します。x <= y が真であれば、その位置にデータを挿入します。ここで、as パターン xs@(y:ys) の変数 xs を使っています。x : xs とすることでリストに x を挿入することができます。
それでは実行してみましょう。
ghci> insert_sort [5,6,4,7,3,8,2,9,1,0] [0,1,2,3,4,5,6,7,8,9] ghci> insert_sort [9,8,7,6,5,4,3,2,1,0] [0,1,2,3,4,5,6,7,8,9] ghci> insert_sort [1,2,3,4,5,6,7,8,9,10] [1,2,3,4,5,6,7,8,9,10]
挿入ソートはデータ数が多くなると実行時間がかかります。データ数を N とすると、実行時間は N の 2 乗に比例します。挿入ソートは簡単ですが遅いアルゴリズムなのです。
次は、高速なアルゴリズムとして有名な「クイックソート (quick sort)」を取り上げます。クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。基準になる値のことを「枢軸」といいます。枢軸は要素の中から適当な値を選んでいいのですが、リストの場合は任意の要素を簡単に選ぶことができません。この場合、いちばん簡単に求めることができる先頭の要素を枢軸とします。
リストを 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]
・・・分割を繰り返していく・・・
図 : クイックソート
このようにリストを分割していくと、最後は空リストになります。ここが再帰の停止条件になります。あとは分割したリストを結合していけばいいわけです。プログラムは次のようになります。
リスト：クイックソート -- リストの分割 partition :: Ord a => (a, [a]) -> ([a],[a]) partition (_, []) = ([], []) partition (x, y:ys) = if y < x then (y:a, b) else (a, y:b) where (a, b) = partition (x, ys) -- クイックソート quick_sort :: Ord a => [a] -> [a] quick_sort [] = [] quick_sort (x:xs) = quick_sort a ++ (x : quick_sort b) where (a, b) = partition (x, xs)
関数 partition はリストを枢軸 x よりも小さい要素とそれ以外の要素の 2 つに分けます。最初の節が空リストの場合です。これが再帰呼び出しの停止条件になります。空リストの場合はタプル ([ ], [ ]) を返します。
次の節でリストを分割します。引数のリストをパターン y : ys で分解し、where 節で partition を再帰呼び出ししてリスト ys を 2 つに分割します。返り値は局所変数 a, b で受け取ります。あとは、枢軸 x と要素 y を比較して、y が x よりも小さければ y をリスト a に追加して返します。そうでなければ、y をリスト b に追加して返します。これで枢軸 x を基準にしてリストを 2 分割することができます。
次は関数 quick_sort を説明します。最初の節が空リストの場合で、再帰呼び出しの停止条件になります。次の節でリストを分割してソートを行います。パターン x : xs でリストを分解し、リストの先頭要素 x を枢軸とします。リストの分割は関数 partition で行います。where 節で partition を呼び出して、返り値を局所変数 a, b で受け取ります。そして、quick_sort を再帰呼び出しして、リスト a, b をソートします。あとは、その結果を枢軸 x を挟んで結合すればいいわけです。
それでは、簡単な実行例を示しましょう。
ghci> quick_sort [5,6,4,7,3,8,2,9,1,0] [0,1,2,3,4,5,6,7,8,9] ghci> quick_sort [0,1,2,3,4,5,6,7,8,9] [0,1,2,3,4,5,6,7,8,9] ghci> quick_sort [9,8,7,6,5,4,3,2,1,0] [0,1,2,3,4,5,6,7,8,9]
正常に動作していますね。
クイックソートの実行時間は、データ数を N とすると平均して N * log2 N に比例します。ところが、枢軸の選び方によっては、最悪で N の 2 乗に比例するところまで劣化します。つまり、挿入ソートと同じくらい遅くなってしまうのです。たとえば、リストの先頭要素を枢軸として選ぶ場合、リストの要素が昇順または降順に並んでいると最悪の結果になります。
このため、クイックソートをプログラムする場合、枢軸の選び方を工夫するのが一般的です。たとえば、データの中からいくつかの要素を選び、その中で中間の値を持つ要素を枢軸に選びます。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は減少しますが、中間の値を選ぶのに時間がかかってしまいます。実際には、3 つから 5 つの要素を選んで、その中で中間の値を枢軸とする場合が多いようです。
ただし、この改良方法はリストには不向きであることに注意してください。リストはデータ数が多くなるほど、後ろのデータを取り出すのに時間がかかるようになります。先頭から 3 つのデータを取り出して枢軸を選んだとしても、降順または昇順に並んだデータには効果が無いのは明らかです。このため、リストのソートはクイックソートよりも「マージソート (merge sort)」の方が適しているといわれています。マージソートについては、あとで取り上げる予定です。
次の関数をパターンを使って書き直してください。
リスト : 問題の解答例 (q03.hs) single :: [a] -> Bool single [_] = True single _ = False double :: [a] -> Bool double [_, _] = True double _ = False longer :: ([a], [a]) -> Bool longer ([], _) = False longer (_, []) = True longer (_:xs, _:ys) = longer (xs, ys) take' :: (Int, [a]) -> [a] take' (_, []) = [] take' (0, _) = [] take' (n, x:xs) = x : take' (n - 1, xs) drop' :: (Int, [a]) -> [a] drop' (_, []) = [] drop' (0, xs) = xs drop' (n, _:xs) = drop' (n - 1, xs) nth :: (Int, [a]) -> a nth (_, []) = error "nth: empty list" nth (0, x:_) = x nth (n, _:xs) = nth (n - 1, xs) sum' :: Num a => [a] -> a sum' [] = 0 sum' (x:xs) = x + sum' xs product' :: Num a => [a] -> a product' [] = 1 product' (x:xs) = x * product' xs
ghci> :l q03.hs [1 of 1] Compiling Main ( q03.hs, interpreted ) Ok, one module loaded. ghci> single [1] True ghci> single [] False ghci> single [1,2] False ghci> double [1,2] True ghci> double [1,2,3] False ghci> double [1] False ghci> double [] False ghci> longer ([1,2,3],[4,5,6]) False ghci> longer ([1,2,3],[4,5]) True ghci> longer ([1,2,3],[4,5,6,7]) False ghci> longer ([],[4,5,6,7]) False ghci> longer ([],[]) False ghci> take' (3,[1,2,3,4,5]) [1,2,3] ghci> take' (0,[1,2,3,4,5]) [] ghci> take' (5,[1,2,3,4,5]) [1,2,3,4,5] ghci> take' (6,[1,2,3,4,5]) [1,2,3,4,5] ghci> drop' (3,[1,2,3,4,5]) [4,5] ghci> drop' (0,[1,2,3,4,5]) [1,2,3,4,5] ghci> drop' (5,[1,2,3,4,5]) [] ghci> drop' (6,[1,2,3,4,5]) [] ghci> nth (0, [1,2,3,4,5]) 1 ghci> nth (1, [1,2,3,4,5]) 2 ghci> nth (2, [1,2,3,4,5]) 3 ghci> nth (4, [1,2,3,4,5]) 5 ghci> nth (5, [1,2,3,4,5]) *** Exception: nth: empty list ghci> sum' [1,2,3,4,5,6,7,8,9,10] 55 ghci> sum' [1,4,9,16,25,36] 91 ghci> product' [1,2,3,4,5,6,7,8,9,10] 3628800 ghci> product' [1,4,9,16,25,36] 518400