人気ブログランキング | 話題のタグを見る

再帰関数の作り方

リストの要素から n 個とる組み合わせを全て列挙するプログラムを例にとって、再帰関数の作り方を考えてみた。

再帰関数を作るときにまず考えるのは、その関数の名前と型だ。再帰関数を作るときは、その関数がまず定義済みだと仮定して考えていくのが便利だからだ。そこでこの関数の名前を comb とすることにするとその型シグネチャーは次のようになる。

comb :: n -> [a] -> [[a]]

つまり、関数 comb は元のリストから取り出す要素の個数とその要素を取り出す元となるリストを引数にとり、組み合わせのリストのリストを戻り地とすることになる。

つぎにやることは、comb の定義の再帰部分 recursive case を考えることだ。これは、comb がすでに定義されていると考えると、定義がしやすくなる。recursive case を定義するために、実際の例でテストをしてみる。[1, 2, 3] というリストから2つの要素を取り出す組み合わせのリストを作ることを考えてみよう。すなわち、comb 2 [1, 2, 3] の再帰部分を考えてみる。

まず、[1, 2, 3] から先頭の要素の 1 を取り出すと 1 と残りの要素 [2, 3] にわけられる。目的の組み合わせのひとつは、この 1 と残りの [2, 3] のうちの一つからなる組み合わせ [[2], [3]] を合わせて [[1, 2], [2, 3]] を作ることだ。しかし、これだけでは十分ではない。組み合わせにはこのほかに、残りのリスト [2, 3] から2つ取る組み合わせ [[2, 3]] も含まれるからだ。したがって、目的の組み合わせは次のような式で表せる。

map (1:) [[2], [3]] ++ [[2, 3]]

これは実際に ghci で計算することができる。

Prelude> map (1:) [[2],[3]] ++ [[2,3]]
[[1,2],[1,3],[2,3]]

上の計算を comb を使って記述してみよう。

comb 2 [1, 2, 3] = map (1:) (comb 1 [2, 3]) ++ comb 2 [2, 3]

これを、次のように一般化すると comb の再帰部分 recursive case が完成する。

comb n (x:xs) = map (x:) (comb (n-1) xs) ++ comb n xs

さらに、この漸化式を使って comb の境界条件 base case を定義する。まず、リスト [1, 2, 3] から1個だけをとりだす組み合わせを考えると、

comb 1 [1, 2, 3] = map (1:) (comb 0 [2,3]) ++ comb 1 [2, 3]

これは [[1], [2], [3]] になるはずだから、

map (1:) (comb 0 [2,3]) ++ comb 1 [2, 3] = [[1], [2], [3]]

である。この式で左辺の comb 0 [2, 3] がどのような値になるのかを考える。comb 1 [2, 3] は [[2], [3]] だから、

map (1:) (comb 0 [2, 3]) = [[1]]

でなければならない。したがって、

comb 0 [2, 3] = [[]]

であることがわかる。comb 0 [2, 3] = [] だと、map (1:) (comb 0 [2, 3]) = [] となって要素の 1 が消し飛んでしまうからだ。このへんの事情は第2引数の [2, 3] がどのようなリストであっても同じである。したがって、次の定義が境界条件 base case の一つとなる。

comb 0 _ = [[]]

さらに、comb n xs の境界条件はもう一つ必要だ。comb のもう一つの引数 xs についての境界条件も必要だからだ。そこで xs = [] となるような場合を考えてみる。これは [1] から1つの要素を取り出す場合、すなわち、comb 1 [1] を考えるとよい。すなわち、

comb 1 [1] = map (1:) (comb 0 []) ++ comb 1 []

である。comb 0 [] = [[]] であるから map (1:) (comb 0 []) = map (1:) [[]] = [1] である。あきらかに comb 1 [1] = [1] だから、

comb 1 [] = []

でなくてはならない。comb 1 [] = [[]] でも良さそうだがそれだと、

comb 1 [1] = [[1], []]

となって、余計な [] が戻り値に混ざってしまう。したがって、 comb 1 [] = [] でなければならない。それでは comb 2 [] の場合などうだろうか。

comb 2 [] = map (:) (comb 1 []) ++ comb 1 []

となっておかしなことになるので、comb 2 [] = [] としなければならない。したがって、一般化して初期条件の2つ目が決まる。すなわち、

comb _ [] = []

である。境界条件を決めることができたので、あらためて comb のプログラムを作ってみてテストしたらうまく動くようだ。

Prelude> :{
Prelude| comb 0 _ = [[]]
Prelude| comb _ [] = []
Prelude| comb n (x:xs) = map (x:) (comb (n-1) xs) ++ comb n xs
Prelude| :}
Prelude> comb 3 [1..4]
[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

このように、再帰関数を定義するときは再帰部分 recursive case を定義するより境界条件 base case を求めるほうが難しい。しかし、再帰関数の引数がどのような場合にも再帰部分の等式が成り立つように考えていくことで、境界条件を求めることができるのだ。

再帰関数の定義は、右辺に自分自身の関数が現れるのでイメージしにくいが、その関数がすでに定義済みであると仮定して、再帰部分、境界部分の順に定義していけばそれぼど難しいものではない。


by tnomura9 | 2018-10-16 08:13 | Haskell | Comments(0)
<< エラトステネスのふるい 再帰関数と畳込み >>