Haskell あれこれ 再帰の種類(リスト型)

2.リスト型

2-1 リスト型の引数の再帰関数

Haskell で再帰的に関数を定義する場合、1)終了条件(base case) がある、2)等式の左側にも定義される関数名が現れる(recursive case)、3)左側の関数の引数は右側の関数の引数よりも小さい(reduce)、という3つの要件がある。数値型の引数を取る関数の場合は、次のように等号の左側の関数の引数が右側のそれより小さい。

fact n = n * fact (n-1)

では、引数がリストの場合はどうかというと、ほとんどの場合が、等号の左側の関数の引数のリストの先頭の要素をとりだして右項に記述する処理になる。右項の式の左項と同名の関数は左項のリストの先頭の要素を除いた残りのリストを引数にとる。文章にすると分かりにくいので、リストの要素のすべてを2倍にする double という関数を定義してみよう。

プログラム
double :: [Int] -> [Int]
double [] = []
double (x:xs) = (x * 2) : double xs

実行例
Main> double [1,2,3]
[2,4,6]

プログラムの double [] = [] が終了条件で、空のリストを2倍しても空のリストだ。

double (x:xs) = (x * 2) : double xs が再帰的定義で、等号の右と左に double という同じ関数が現われている。等号右のパターン (x:xs) は引数のリストの最初の要素を x に、残りのリストを xs にバインドすることを意味している。左の処理では、x を2倍して、リスト double xs に連結している。この時点で左の double に渡された引数のリスト (x:xs) はひとつ短くなって xs として右の double に渡されている。

このあたりの動作は、次のように再帰的定義を展開するとよくわかる。

doble [1,2,3] = (1*2) : doble [2,3] = 2 : ((2*2) : double [3]) = 2:(4:((3*2):double[])))

= 2:(4:(6:[])) = [2,4,6]

となるので、最終的に [2,4,6] のリストが戻り値になるということが分かる。

2ー2 ワイルドカード

2ー1の例ではリストの先頭の要素を取り出すパターンに (x:xs) を使った。しかし、先頭の要素 x を取り出してもそれを利用しない場合がある。そういうときは、x の代わりに _ (ワイルドカード) を使う。次の例はリストの長さを調べる mylength という関数だ。

mylength :: [a] -> Int
mylength [] = 0
mylength (_:xs) = 1 + mylength xs

実行例
Main> mylength [1,2,3]
3

1行目が関数の型の宣言で、2行目が終了条件、3行目が再帰的定義だが、等号の右側のパターンに (_:xs) が使われている。(x:xs) の代わりにワイルドカードが使われているのは、等号左の定義式に取り出した要素のデータは使わないからだ。要素の取り出しが大切で、取り出しても使わないような場合は、この様にワイルドカードを用いる。

2ー3 複数の引数がある場合

リストが引数の再帰関数は、複数の引数をとることができる。次の例は第1引数を昇順にソートされた第2引数のリストに挿入する関数だ。

insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys) | x <= y = x : y : ys
                | otherwise = y : insert x ys

実行例
Main> insert 5 [2,4..10]
[2,4,5,6,8,10]

上のプログラムの Ord a => という記述は、関数の定義に要素の大小関係が使われるため、要素の型が Ord クラスに属することを意味している。

次の例は、第1引数のリストと第2引数のリストの要素のペアのタプルのリストをつくる、myzip という関数だ。複数のリストを引数にとる再帰関数の例だ。

myzip :: [a] -> [b] -> [(a,b)]
myzip [] _ = []
myzip _ [] = []
myzip (x:xs) (y:ys) = (x,y) : zip xs ys

実行例
Main> myzip [1,2,3] [4,5,6]
[(1,4),(2,5),(3,6)]

このように、引数がリスト型の再帰関数も、(x:xs)、(_:xs) 、_ (ワイルドカード) という三つのパターンを知っていれば大抵のものが自分で書けるだろう。
[PR]
by tnomura9 | 2009-08-20 18:10 | Haskell | Comments(0)
<< Haskell あれこれ 再帰... Haskell あれこれ 再帰... >>