M.Hiroi's Home Page

Functional Programming

お気楽 Haskell プログラミング入門

[ PrevPage | Haskell | NextPage ]

パターンマッチングとガード

●定数と変数はパターンになる

関数を定義する場合、引数に「パターン (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)

実引数を定数ではなく範囲で場合分けしたいときは「ガード (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 は型チェックを厳密に行う関数型言語ですが、型推論、多相型関数、パターンなどの機能により、とても柔軟にプログラミングすることができます。

●case 式

パターンは 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 を挿入することができます。

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

*Main> insert_sort [5,6,4,7,3,8,2,9,1,0]
[0,1,2,3,4,5,6,7,8,9]
*Main> insert_sort [9,8,7,6,5,4,3,2,1,0]
[0,1,2,3,4,5,6,7,8,9]
*Main> 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 を挟んで結合すればいいわけです。

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

*Main> quick_sort [5,6,4,7,3,8,2,9,1,0]
[0,1,2,3,4,5,6,7,8,9]
*Main> quick_sort [0,1,2,3,4,5,6,7,8,9]
[0,1,2,3,4,5,6,7,8,9]
*Main> 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)」の方が適しているといわれています。マージソートについては、あとで取り上げる予定です。

●問題

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

  1. リスト xs の要素がただひとつか調べる述語 single xs
  2. リスト xs の要素が二つあるか調べる述語 double xs
  3. リスト xs はリスト ys よりも長いとき真を返す関数 longer (xs, ys)
  4. リスト xs の先頭から n 個の要素を取り出す関数 take' (n, xs)
  5. リスト xs の先頭から n 個の要素を取り除く関数 drop' (n, xs)
  6. リスト xs の n 番目の要素を求める関数 nth (n, xs)
  7. リスト xs の要素を足し算する関数 sum' xs
  8. リスト xs の要素を掛け算する関数 product' xs












●解答

リスト : 問題の解答例 (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
Prelude> :l q03.hs
[1 of 1] Compiling Main             ( q03.hs, interpreted )
Ok, one module loaded.
*Main> single [1]
True
*Main> single []
False
*Main> single [1,2]
False

*Main> double [1,2]
True
*Main> double [1,2,3]
False
*Main> double [1]
False
*Main> double []
False

*Main> longer ([1,2,3],[4,5,6])
False
*Main> longer ([1,2,3],[4,5])
True
*Main> longer ([1,2,3],[4,5,6,7])
False
*Main> longer ([],[4,5,6,7])
False
*Main> longer ([],[])
False

*Main> take' (3,[1,2,3,4,5])
[1,2,3]
*Main> take' (0,[1,2,3,4,5])
[]
*Main> take' (5,[1,2,3,4,5])
[1,2,3,4,5]
*Main> take' (6,[1,2,3,4,5])
[1,2,3,4,5]

*Main> drop' (3,[1,2,3,4,5])
[4,5]
*Main> drop' (0,[1,2,3,4,5])
[1,2,3,4,5]
*Main> drop' (5,[1,2,3,4,5])
[]
*Main> drop' (6,[1,2,3,4,5])
[]

*Main> nth (0, [1,2,3,4,5])
1
*Main> nth (1, [1,2,3,4,5])
2
*Main> nth (2, [1,2,3,4,5])
3
*Main> nth (4, [1,2,3,4,5])
5
*Main> nth (5, [1,2,3,4,5])
*** Exception: nth: empty list

*Main> sum' [1,2,3,4,5,6,7,8,9,10]
55
*Main> sum' [1,4,9,16,25,36]
91

*Main> product' [1,2,3,4,5,6,7,8,9,10]
3628800
*Main> product' [1,4,9,16,25,36]
518400

初版 2013 年 1 月 13 日
改訂 2021 年 1 月 7 日

高階関数

Lisp. ML, Haskell などの関数型言語は、関数を他のデータ型と同等に取り扱うことができます。つまり、関数を変数に代入したり、引数として渡すことができます。また、値として関数を返すこともできるので、関数を作る関数を定義することもできます。関数を引数にとる関数のことを「汎関数 (functional)」とか「高階関数 (higher order function)」と呼びます。

Haskell は高階関数を簡単に定義することができます。もちろん、値として関数を返すこともできるので、関数を作る関数を定義することも簡単です。実際、関数の操作は Common Lisp よりも柔軟で簡単です。

●関数を引数にとる関数

簡単な例として、整数 n から m までの和を求める関数 sum_of_integer を作ってみましょう。プログラムは次のようになります。

リスト : 整数の和

sum_of_integer :: (Integer, Integer) -> Integer
sum_of_integer (n, m)
  | n > m     = 0
  | otherwise = n + sum_of_integer (n + 1, m)

実行例を示します。

*Main> sum_of_integer (1, 10)
55
*Main> sum_of_integer (1, 100)
5050

プログラムは簡単なので説明は不要でしょう。それでは、整数の 2 乗の和と 3 乗の和を求めるプログラムはどうなるでしょうか。次のリストを見てください。

リスト : 整数の 2 乗の和と 3 乗の和

-- 2 乗
square :: Num a => a -> a
square x = x * x

-- 3 乗
cube :: Num a => a -> a
cube x = x * x * x

-- 2 乗の和
sum_of_square :: (Integer, Integer) -> Integer
sum_of_square (n, m)
  | n > m     = 0
  | otherwise = square n + sum_of_square (n + 1, m)

-- 3 乗の和
sum_of_cube :: (Integer, Integer) -> Integer
sum_of_cube (n, m)
  | n > m     = 0
  | otherwise = cube n + sum_of_square (n + 1, m)

実行例を示します。

*Main> sum_of_square (1, 10)
385
*Main> sum_of_square (1, 100)
338350
*Main> sum_of_cube (1, 10)
3025
*Main> sum_of_cube (1, 100)
25502500

n を加算する処理で、関数 square を呼び出すと 2 乗の和、関数 cube を呼び出すと 3 乗の和を求めることができます。関数 sum_of_square と sum_of_cube の違いはこれだけです。ここで、square や cube を引数として渡すことができれば、sum_of_square や sum_of_cube を一つの関数で済ますことができます。次のリストを見てください。

リスト : 高階関数 sum_of

sum_of :: (Integer -> Integer, Integer, Integer) -> Integer
sum_of (f, n, m)
  | n > m     = 0
  | otherwise = f n + sum_of (f, n + 1, m)

関数 sum_of の引数 f に関数を渡します。渡された関数は、今までと同じ方法で呼び出すことができます。square や cube のかわりに f n + sum_of ... とすることで、関数 f に整数 n を適用した結果を sum_of の返り値に加算することができます。

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

*Main> sum_of (square, 1, 10)
385
*Main> sum_of (cube, 1, 10)
3025

●ラムダ式

高階関数を使うようになると、数を 2 乗する square のような小さな関数をいちいち定義するのが面倒になります。とくに、その高階関数でしか使わないのであれば、なおさらそう思うでしょう。Haskell には Lisp と同様の「ラムダ式」という名前のない関数が用意されています。

Haskell の場合、ラムダ式は次のように定義します。

\ 引数 -> 式

関数定義はラムダ式を用いて次のように表すことができます。

func = \ 引数 -> 式

ラムダ式は関数型のデータを生成して返します。そして、関数定義は変数 func をその値に束縛するだけなのです。また、Haskell はラムダ式をそのまま実行することができますし、関数の引数にラムダ式を渡すこともできます。

簡単な例を示します。

*Main> (\x -> x * x) 5
25
*Main> (\(x,y) -> x + y) (1, 2)
3
*Main> sum_of (\x -> x * x, 1, 10)
385

●カリー化関数

ところで、今まではタプルを使って複数の引数を受け取る関数を実現しましたが、Haskell にはもう一つ方法があります。関数型言語は関数をデータ型の一つとして扱うことができるので、関数の返り値として関数を返すことができます。この「関数を返す関数」を使うと、関数の引数が一つでも複数の引数を処理することができます。このような関数を「カリー化関数 (curried function)」といいます。

たとえば、\(x, y) -> x + y の場合、引数 x を受け取ると「引数 y を受け取って x + y を計算する関数」を返し、その関数に引数 y を渡せば x + y を計算することができます。Haskell では、次のように定義することができます。

*Main> :t \x -> \y -> x + y
\x -> \y -> x + y :: Num a => a -> a -> a

関数の型が少し複雑になりました。-> は右結合なので、a -> a -> a は a -> (a -> a) となります。これは引数 a を受け取り、a -> a という型の関数を返すことを表しています。これで引数を一つだけ与えれば、関数を返すことになります。もちろん、引数を 2 つ与えれば、それらを加算した結果を返します。つまり、最初の引数を受け取って関数を生成し、その関数を 2 番目の引数に適用する、という動作になります。

それでは実際に試してみましょう。

*Main> :t (\x -> \y -> x + y) 1
(\x -> \y -> x + y) 1 :: Num a => a -> a
*Main> (\x -> \y -> x + y) 1 2
3

引数を一つだけ渡すと「引数 y を受け取って x + y を計算する関数」を返します。引数を 2 つ渡すと、それを足し算した値を返します。カリー化関数の場合、引数は空白で区切ることに注意してください。

ラムダ式を入れ子にするのは面倒なので、Haskell は次のようにカリー化関数を定義することができます。

\ 引数1 引数2 ... 引数n -> 式

また、関数定義でも同様にカリー化関数を定義することができます。

名前 引数1 引数2 ... 引数n = 式

関数をカリー化する場合、引数をカッコで囲わず、カンマでも区切りません。たとえば、関数 sum_of をカリー化すると次のようになります。

リスト : 関数 sum_of のカリー化

sum_of' :: (Integer -> Integer) -> Integer -> Integer -> Integer
sum_of' f n m
  | n > m     = 0
  | otherwise = f n + sum_of' f (n + 1) m

そして、この sum_of' を使うと、sum_of_integer, sum_of_square, sum_of_cube を簡単に定義することができます。

*Main> sum_of_integer' = sum_of' id
*Main> sum_of_square' = sum_of' square
*Main> sum_of_cube' = sum_of' cube
*Main> :t sum_of_integer'
sum_of_integer' :: Integer -> Integer -> Integer
*Main> :t sum_of_square'
sum_of_square' :: Integer -> Integer -> Integer
*Main> :t sum_of_cube'
sum_of_cube' :: Integer -> Integer -> Integer
*Main> sum_of_integer' 1 10
55
*Main> sum_of_square' 1 10
385
*Main> sum_of_cube' 1 10
3025

sum_of_integer', sum_of_square', sum_of_cube' は引数 s, e を省略して定義していますね。このような関数定義を「ポイントフリースタイル」といいます。関数 g の定義が g x = f x とすると、引数 x のことを「ポイント」と呼びます。この場合、引数 x を省略して関数定義を g = f と表すことができます。

sum_of_cube' の場合、引数を記述すると次のようになります。

   sum_of_cube' s e = sum_of' cube s e
=> sum_of_cube' s = sum_of' cube s
=> sum_of_cube' = sum_of' cube

右辺と左辺で最後の引数は同じ e なので、省略することが可能です。e を省略したあと、右辺左辺ともに最後の引数は s になりますね。これも省略することができます。したがって、関数定義は sum_of_cube' = sum_of' cube となります。

このように、カリー化された関数の一部の引数に値を与えて、残りの引数を受け取る関数を生成することを「部分適用 (partial application)」といいます。カリー化関数は部分適用が簡単にできるのでとても便利です。Haskell の場合、カリー化関数はよく使われる方法です。

●リストの生成

Haskell は数列を表すリストを簡単に生成することができます。この機能を「レンジ (range)」といいます。構文は次のようになります。

(1) [s .. e] => [s, s+1, s+2, ..., e-1, e]
(2) [s, s+a, .. e] => [s, s+a, s+a*2, s+a*3, ..., e]

(1) のように開始 s と終了 e の値 (s < e) を指定すると、s 以上 e 以下の数列が生成されます。s > e の場合は空リストになります。簡単な例を示しましょう。

Prelude> [1 .. 10]
[1,2,3,4,5,6,7,8,9,10]
Prelude> [10 .. 1]
[]

(2) は初項と第 2 項で差分を指定します。つまり、公差 a の等差数列になります。差分が負の場合、s < e は空リストになります。簡単な例を示しましょう。

Prelude> [1,3 .. 10]
[1,3,5,7,9]
Prelude> [1,4 .. 10]
[1,4,7,10]
Prelude> [10, 9 .. 1]
[10,9,8,7,6,5,4,3,2,1]
Prelude> [10, 9 .. 11]
[]

レンジは整数だけではなく型クラス Enum のインスタンスであれば使用することができます。簡単な例を示します。

Prelude> ['a' .. 'z']
"abcdefghijklmnopqrstuvwxyz"
Prelude> ['a', 'c' .. 'z']
"acegikmoqsuwy"
Prelude> [1.0 .. 10.0]
[1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0]
Prelude> [1.0, 1.25 .. 2.0]
[1.0,1.25,1.5,1.75,2.0]

このように、Haskell ではレンジを使ってリストを簡単に生成することができます。

●セクション

Haskell は中置演算子をカッコで囲むとカリー化関数として扱うことができます。簡単な例を示しましょう。

*Main> (+) 1 2
3
*Main> (*) 1 2
2
*Main> (^) 2 3
8

中置演算子の場合、部分適用には特別な構文が用意されています。次の例を見てください。

*Main> (+1) 2
3
*Main> (*10) 2
20
*Main> (^2) 3
9
*Main> (2^) 3
8

演算子を op, 引数を x, y とすると、 (op y) x は x op y を意味し、(y op) x は y op x を意味します。この機能を「セクション」と呼びます。高階関数を使う場合、セクションはとても役に立ちます。たとえば、sum_of_square, sum_of_cube は次のように定義できます。

リスト : sum_of_square, sum_of_cube の定義

sum_of_square = sum_of' (^2)
sum_of_cube   = sum_of' (^3)

なお、演算子 - を部分適用することはできません。(-2) は -2 という負の数として解釈されます。ご注意くださいませ。

●問題

次の関数をカリー化関数を使って定義してください。

  1. リスト xs, ys を連結する関数 append xs ys
  2. リスト xs はリスト ys よりも長いとき真を返す関数 longer xs ys
  3. リスト xs の先頭から n 個の要素を取り出す関数 take' n xs
  4. リスト xs の先頭から n 個の要素を取り除く関数 drop' n xs
  5. リスト xs の n 番目の要素を求める関数 nth n xs
  6. リスト xs から x を探索する関数 member x xs
  7. リスト xs から述語 pred が真を返す要素を探索する関数 member_if pred xs
  8. リスト xs を述語 pred の真偽で二分割する関数 partition_if pred xs
  9. s 以上 e 以下の整数列を生成する関数 iota s e
  10. s 以上 e 以下の整数列に関数 f を適用した結果をリストに格納して返す関数 tabulate f s e












●解答

リスト : 問題の解答例 (q04.hs)

append :: [a] -> [a] -> [a]
append [] ys = ys
append (x:xs) ys = x : append xs ys

longer :: [a] -> [a] -> Bool
longer [] _ = False
longer _ [] = True
longer (_:xs) (_:ys) = longer xs ys

take' :: Int -> [a] -> [a]
take' 0 _ = []
take' _ [] = []
take' n (x:xs) = x : take' (n - 1) xs

drop' :: Int -> [a] -> [a]
drop' 0 xs = xs
drop' _ [] = []
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

member :: Eq a => a -> [a] -> [a]
member _ [] = []
member x xs@(y:ys)
  | x == y      = xs
  | otherwise   = member x ys

member_if :: (a -> Bool) -> [a] -> [a]
member_if _ [] = []
member_if pred ys@(x:xs)
  | pred x    = ys
  | otherwise = member_if pred xs

partition_if :: (a -> Bool) -> [a] -> ([a],[a])
partition_if _ [] = ([], [])
partition_if pred (x:xs) =
  if pred x then (x:a, b) else (a, x:b)
  where (a, b) = partition_if pred xs

iota :: Integral a => a -> a -> [a]
iota s e
  | s > e = []
  | otherwise = s : iota (s + 1) e

tabulate :: Integral a => (a -> b) -> a -> a -> [b]
tabulate f s e
  | s > e = []
  | otherwise = f s : tabulate f (s + 1) e

Prelude> :l q04.hs
[1 of 1] Compiling Main             ( q04.hs, interpreted )
Ok, one module loaded.

*Main> append [1,2,3] [4,5,6]
[1,2,3,4,5,6]
*Main> append [1,2,3] []
[1,2,3]
*Main> append [] [4,5,6]
[4,5,6]

*Main> longer [1,2,3] [4,5,6]
False
*Main> longer [1,2,3] [4,5]
True
*Main> longer [1,2,3] [4,5,6,7]
False

*Main> take' 3 [1,2,3,4,5]
[1,2,3]
*Main> take' 0 [1,2,3,4,5]
[]
*Main> take' 5 [1,2,3,4,5]
[1,2,3,4,5]

*Main> drop' 3 [1,2,3,4,5]
[4,5]
*Main> drop' 0 [1,2,3,4,5]
[1,2,3,4,5]
*Main> drop' 5 [1,2,3,4,5]
[]

*Main>> nth 0 [1,2,3,4,5]
1
*Main>> nth 2 [1,2,3,4,5]
3
*Main>> nth 4 [1,2,3,4,5]
5
*Main>> nth 5 [1,2,3,4,5]
*** Exception: nth: empty list

*Main>> member 1 [1,2,3,4,5]
[1,2,3,4,5]
*Main>> member 5 [1,2,3,4,5]
[5]
*Main>> member 6 [1,2,3,4,5]
[]

*Main>> member_if (\x -> x > 3) [1,2,3,4,5]
[4,5]
*Main>> member_if (\x -> x < 2) [1,2,3,4,5]
[1,2,3,4,5]
*Main>> member_if (\x -> x < 0) [1,2,3,4,5]
[]

*Main>> partition_if even [1,2,3,4,5,6,7,8]
([2,4,6,8],[1,3,5,7])
*Main>> partition_if odd [1,2,3,4,5,6,7,8]
([1,3,5,7],[2,4,6,8])
*Main>> partition_if (\x -> x > 4) [1,2,3,4,5,6,7,8]
([5,6,7,8],[1,2,3,4])

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

*Main>> tabulate (*10) 1 10
[10,20,30,40,50,60,70,80,90,100]
*Main>> tabulate (^2) 1 10
[1,4,9,16,25,36,49,64,81,100]

初版 2013 年 1 月 13 日
改訂 2021 年 1 月 7 日

Copyright (C) 2013-2021 Makoto Hiroi
All rights reserved.

[ PrevPage | Haskell | NextPage ]