再帰関数
再帰関数とは
Haskell では関数やデータの再帰的定義がよく使われる。この再帰的定義の仕組みが最初は理解するのが難しいことが多く、Haskell を学ぶのに壁があるとすれば、最大の壁はこの再帰的定義だろう。
一般に関数の定義は、f(x)＝x*x のように左に関数名と変数(引数）右に関数の値（戻り値）の計算法が記述される。Haskell の関数は数学の場合とほぼ同じやり方で定義される。たとえば、引数に整数をとり戻り値にその2乗を返す関数 square は、
square x = x * x
で定義できる。この場合、関数の名前は式の左側にしか現れない。新しい関数を定義するのに既に動作が確定している操作を組み合わせるわけで納得できる。ところが、関数の再帰的定義の最大の特徴はこの関数名が式の右側にも現れると言うことだ。例えば階乗の計算の再帰的定義 (recursive case) は次のようになる。
fact n = n * fact (n-1)
関数を定義するのに、まだ定義のはっきりしていない自分自身を使うという変な定義のしかたなので奇妙な感じがする。しかし、よく見ると等式の左と右では関数の引数の値が違う。これは、どういう意味なのだろうか。たとえば、n = 4 の場合を考えてみよう。
fact 4 = 4 * fact 3 = 4 * (3 * fact 2) = 4 * (3 * (2 * fact1)) = ...
のように右の関数を左の定義で置き換えていくことによって、関数の定義がつぎつぎに展開されていくのが分かる。この時に右側に現れる fact n の引数は常に左側の fact の引数より一つだけ小さい (reduce) ことに注意する。このままでは、関数の展開は永遠に続いてしまうが、fact n の定義で、fact 1 = 1 という終了条件（base case) が与えられていると、上の定義は有限回で終了する。つまり、
fact 4 = 4 * fact 3 = 4 * (3 * fact 2) = 4 * (3 * (2 * fact 1) = 4 * (3 *(2 * 1)) = 24
のように定義を展開する度に fact の引数が減少していき、ついには終了条件に達してすべての展開が数値にかわり、定義が終了する。この様に定義の展開が有限回で終了すればあとは展開された数式を計算することによって、fact 4 の値を決定することができる。関数を定義するのに自分自身を使ってもちゃんと値が求められる仕組みがあるのだ。
再帰的定義の条件
関数の定義に定義される関数自身を使うという再帰的定義の変則的な定義法だが次の二つの要件を満たして入れば、きちんと動作する。
１）明示的な終了条件 (base case) があること。
２）等号の右の関数を定義するのに左の関数を使うとき (recursive case) は、左の関数の引数の値が減少 (reduce) している必要があること。
この二つの要件をおさえていれば、関数を定義するのに、定義する当の自分自身を使うという理解しがたい再帰的定義の仕組みを分かって、複雑な現象をコンパクトに記述できる再帰的定義のパワーを活用することができる。
ちなみに、上の fact 関数のHaskell によるプログラムは次のようになる。
fact 1 = 1 fact n = n * fact (n-1)
また、再帰的定義を展開するのに、右の関数を左の定義で置き換えるという操作を続けたが、同じ値の式を置き換えるというのが Haskell の本質的な動作だ。置き換えられた式は常に同じ値をとるので、式の評価が実行の順序によらない、プログラムの正しさや、アルゴリズムの改良を数学的に検証できるなどという関数言語の特徴が現れてくる。
Haskell の再帰関数の種類
Haskell の関数で再帰的定義をする場合引数の型の種類によって分類するのが便利だ。引数の型の種類とは、数値型、リスト型、木構造型 の3つだ。
数値型の引数をとる再帰関数の代表は、階乗だ。階乗を求める関数 fact (x) はつぎのように定義される。
この定義で行くと、fact (0) = 1 だ。引数が０以上の場合はたとえば、fact (4) は、
のように展開が進み終了条件に達した時点で数値の計算が始まる。このような関数はC言語でもプログラムすることができる。
/* 階乗n!を計算する */ 自分自身を、自分自身の中から呼び出すという理解しがたい再帰呼び出しをおこなっているが、これは、関数呼び出しに伴うスタック操作というC言語の実装の仕組み利用して巧みに上で述べた式の展開と同じような効果を作っている。
しかし、実装のことは知らなくてもC言語で再帰呼び出しができるのは分かっているので、簡単な再帰関数なら、そう悩まなくてもC言語でプログラムすることができる。
ところで、この関数 fact (x) を Haskell でプログラムすると次のようになる。
型の定義はしておいたほうが便利だが、慣れないうちは省略してもかまわない。そうすると、これは、上の数学的な定義をそのまま逐語的にプログラムに直しただけだ。if ~ then ~ else 文がないが、Haskell は関数を定義するときに引数のパターンで値を変えることができるからだ。
上のプログラムで２行目は引数が 0 の時の値を設定している。次の行は n | n > 0 が引数のパターンで n が正の整数の場合をあらわしている。
したがって上のプログラムでは、fact 関数の引数が 0 の時は整数 1 が返される。また、引数が正の整数のときは、fact n = n * fact (n-1) = n * (n-1) * fact (n-2) = ... という式の展開が終了条件の fact 0 が現れるまで実行され、終了条件の fact 0 が現れた時点で、展開式の fact 0 が 1 に置き換えられ、計算が始まってその値が整数値として返される。
普通の文章で表すと上のプログラムの説明がやけに長くなってしまったが、再帰的定義が、展開したときの煩雑な手続きをコンパクトに表現してくれるからだ。
いずれにせよ、引数が数値の場合の関数の再帰的定義は、Haskell の場合は、引数のパターン表記を利用して、定義の数式をほぼそのままの形でプログラムできる。また、Haskell のプログラムに引数が数値型の再帰関数が現れたら。f（x）のような数学の表記に直して数式を展開していくとその意味がよく分かる。
Haskell で再帰的に関数を定義する場合、
１）終了条件(base case) がある。 という3つの要件がある。数値型の引数を取る関数の場合は、次のように等号の左側の関数の引数が右側のそれより小さい。
fact n = n * fact (n-1)
では、引数がリストの場合はどうかというと、ほとんどの場合が、等号の左側の関数の引数のリストの先頭の要素をとりだして右項に記述する処理になる。右項の式の左項と同名の関数は左項のリストの先頭の要素を除いた残りのリストを引数にとる。文章にすると分かりにくいので、リストの要素のすべてを2倍にする double という関数を定義してみよう。
プログラム
実行例
プログラムの double [] = [] が終了条件で、空のリストを2倍しても空のリストだ。
double (x:xs) = (x * 2) : double xs が再帰的定義で、等号の右と左に double という同じ関数が現われている。等号右のパターン (x:xs) は引数のリストの最初の要素を x に、残りのリストを xs にバインドすることを意味している。左の処理では、x を2倍して、リスト double xs に連結している。この時点で左の double に渡された引数のリスト (x:xs) はひとつ短くなって xs として右の double に渡されている。
このあたりの動作は、次のように再帰的定義を展開するとよくわかる。
double [1,2,3] = (1*2) : double [2,3] = 2 : ((2*2) : double [3]) = 2:(4:((3*2):double[])))
= 2:(4:(6:[])) = [2,4,6]
となるので、最終的に [2,4,6] のリストが戻り値になるということが分かる。
2ー1の例ではリストの先頭の要素を取り出すパターンに (x:xs) を使った。しかし、先頭の要素 x を取り出してもそれを利用しない場合がある。そういうときは、x の代わりに _ (ワイルドカード) を使う。次の例はリストの長さを調べる mylength という関数だ。
実行例
1行目が関数の型の宣言で、2行目が終了条件、3行目が再帰的定義だが、等号の右側のパターンに (_:xs) が使われている。(x:xs) の代わりにワイルドカードが使われているのは、等号左の定義式に取り出した要素のデータは使わないからだ。要素の取り出しが大切で、取り出しても使わないような場合は、この様にワイルドカードを用いる。
リストが引数の再帰関数は、複数の引数をとることができる。次の例は第１引数を昇順にソートされた第2引数のリストに挿入する関数だ。
実行例
上のプログラムの Ord a => という記述は、関数の定義に要素の大小関係が使われるため、要素の型が Ord クラスに属することを意味している。
次の例は、第1引数のリストと第2引数のリストの要素のペアのタプルのリストをつくる、myzip という関数だ。複数のリストを引数にとる再帰関数の例だ。
実行例
このように、引数がリスト型の再帰関数も、(x:xs)、(_:xs) 、_ (ワイルドカード) という三つのパターンを知っていれば大抵のものが自分で書けるだろう。
普通の用途でプログラムするときに、木構造のデータを使うような機会はあまりない。人工知能や、プログラム言語のパーサなどで利用されるデータ型だ。したがって、木構造が何かという説明はここではしない。Scheme などでは木構造はリストで表現するが、Haskell の場合はユーザデータ型の定義が必要だ。
単純な二分木構造で、ノードに値を持つ木構造は、Haskell では次のように定義する。
上の定義の Tree はタイプコンストラクタで関数の型宣言の時に使われる。Leaf と Node はデータコンストラクタで引数を取る関数のようにふるまう。例えば、Leaf 1 とするとノードの値が１の葉のデータを生成し、Node (Leaf 1) 2 (Leaf 3) とすると、ノードの値が２で左の枝に値1の葉がつながり、右の枝に値3の枝がつながるノードを生成する。
データの宣言で等号の左側にも Tree 型が使われているのに注意してほしい。Haskell ではデータもまた、再帰的に定義できる。Node型は、その中にTree型の左の部分木、ノードの値、Tree型の右の部分木を収めている。
また、deriving Show として、Tree データ型を Show クラスのインスタンスに登録しておくと、Hugs のコンソールでデータを表示できるようになる。このようにしてできる木構造を次に示す。
この木構造を処理するプログラムも再帰的プログラムになることが多い。左の枝を処理したあと、右の枝を処理する、その枝についてもそのノードについて同じ処理を左と右の枝に加える... というような同じ操作を次々に下位レベルのノードについて加えていくからだ。
数値型やリスト型の再帰関数については3つの要件があった。すなわち、１）終了条件(base case)があること、２）関数が再帰的に定義されていること(recursive case)、３）左側の引数の値が右に比べ減少(reduce)していることだ。このうちリスト構造と前二者の場合の違いは、リストのデータが枝分かれしているということだ、引数の減少は右と左の枝の両方にわかれて行われる。このため、再帰的定義の関数名は、等号の左側で2回現れることになる。
文章では分かりにくいので、木構造型を再帰的に処理する関数の例として、ノードの値をすべて集めてリストにする関数 flatten を作ってみる。
実行例
上のプログラムで、2行目が終了条件だ。葉のノードは枝をもたないのでそれ以上は枝をたどれない。3行目が flatten 関数の再帰的定義で、ノードから左の部分木とノードの値と右のの部分木をとりだし、左の部分木にflatten を適用した、flatten l の戻り値のリストとノードの値のリストと、右の部分木の flatten r の戻り値のリストを連結している、引数の減少については、現在のノードを処理して残りの左右の部分木に flatten を適用するので、左側では木構造データからノードが一つ取り去られている勘定になる。
例によって再帰関数の動作を展開によって追いかけてみよう。ただし、木構造の表示は Haskell 流だと煩雑なので、Scheme 流のリストで表現する。
このように再帰関数の動作は数式の展開と同一視してイメージしておくとその動作がよく理解できる。木構造の再帰関数は、等号の左側に関数名が2回現れるので混乱するが、再帰関数の終了条件、再帰的定義、引数の減少の3点をおさえていれば動作の理解がしやすい。
数値型
fact (x) = | 0 (x = 0 のとき)
| n * fact (n-1) (x > 0 のとき）
fact (4) = 4 * fact(3) = 4 * (3 * fact(2)) = 4 * (3 * (2 * fact(1)))
= 4 * (3 * (2 * (1 * fact(0)))) = 4 * (3 * (2 * (1 * 1)))) = 24
int fact(int n) {
if (n==0) return 1; /* 脱出条件。0!は1である */
else return fact(n-1)*n; /* n!は(n-1)!にnを乗じたもの。再帰呼び出し */
} （Wikipedia 「再帰」 より引用）
fact :: Integer -> Integer
fact 0 = 1
fact n | n > 0 = n * fact (n-1)
リスト型
リスト型の引数の再帰関数
２）等式の左側にも定義される関数名が現れる(recursive case)。
３）左側の関数の引数は右側の関数の引数よりも小さい(reduce)
double :: [Int] -> [Int]
double [] = []
double (x:xs) = (x * 2) : double xs
Main> double [1,2,3]
[2,4,6]
ワイルドカード
mylength :: [a] -> Int
mylength [] = 0
mylength (_:xs) = 1 + mylength xs
Main> mylength [1,2,3]
3
複数の引数がある場合
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]
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)]
木構造型
data Tree = Leaf Int | Node Tree Int Tree
deriving Show
木構造型データの例
Main> (Node (Leaf 1) 2 (Node (Leaf 3) 4 (Leaf 5)))
Node (Leaf 1) 2 (Node (Leaf 3) 4 (Leaf 5))
木構造データの再帰関数
flatten :: Tree -> [Int]
flatten (Leaf n) = [n]
flatten (Node l n r) = flatten l ++ [n] ++ flatten r
Main> flatten (Node (Leaf 1) 2 (Node (Leaf 3) 4 (Leaf 5)))
[1,2,3,4,5]
再帰関数の展開
flatten ((1) 2 ((3) 4 (5)))
= flatten (1) ++ [2] ++ flatten ((3) 4 (5))
= [1] ++ [2] ++ (flatten (3) ++ [4] ++ flatten (5))
= [1] ++ [2] ++ ([3] ++ [4] ++ [5])
= [1,2,3,4,5]