- 2022/9/18
- 「末尾再帰最適化」を「末尾呼び出し最適化」に修正
- 「サンク」関連の怪しい言い回しを修正
- その他微妙な表現を修正
Haskellのような純粋関数型プログラミング言語では基本破壊的代入が許されていないために、ループするための構文、または式が用意されていない。そのために、再帰を使ってループを表現する、というのが一般的となっている。
しかし、手続き型言語に慣れたプログラマからすれば、それはとても不安になることでもある。今回、なぜ不安になるのかどうかについて解説するとともに、なぜHaskellでは再帰を用いても問題ないのか書いていこうと思う。
再帰とは
まず再帰とはプログラミングにおけるテクニックの一つで、関数内で自分自身を呼び出す手法を示す。
たとえばPythonで再帰関数を用いて総和（sum）を求める関数を書くと、以下のようになる。
def org_sum(num_list): if len(num_list) == 0: return 0 else: return num_list[0] + org_sum(num_list[1:])
>>> org_sum([1, 2, 3, 4, 5]) # [1..5]のリストの総和を求める 15
Pythonの場合return文で関数の戻り値を指定するのだが、そこにnum_list[0]と自身の戻り値を加算した結果を返すようにしている。
return num_list[0] + org_sum(num_list[1:])
そしてnum_listはリストであり、要素数が0である場合関数は0を返す。
if len(num_list) == 0: return 0
ここで、自身を返す際にnum_list[1:]でnum_list[0]を除いたリストを渡している。
return num_list[0] + org_sum(num_list[1:]) ~~~~~~~~~~~~~~~~~~~~~ ここの部分
つまりorg_sum([1, 2, 3, 4, 5])を式として展開すると、以下のようになる。
return 1 + org_sum([2,3,4,5]) -> 1 + 2 + org_sum([3,4,5]) -> 1 + 2 + 3 + org_sum([4,5]) -> 1 + 2 + 3 + 4 + org_sum([5]) -> 1 + 2 + 3 + 4 + 5 + org_sum([]) -> 1 + 2 + 3 + 4 + 5 + 0 -> 1 + 2 + 3 + 4 + 5 -> 1 + 2 + 3 + 9 -> 1 + 2 + 12 -> 1 + 14 -> 15
以上から、再帰を使えば破壊的代入を行うことなくループを行えることがわかる。なぜなら、以下のようなループで必要となるanswerなどが必要なくなるからである。
def org_sum(num_list): answer = 0 for num in num_list: answer += num return answer
このように破壊的代入を極力なくそうというのは関数型プログラミングの特徴としてよく挙げられる。破壊的代入を極力なくすことで、変数などの状態管理の手間を抑えることができる。
しかし再帰には欠点もある
なんだよ、再帰最高じゃん！手続き型言語でも多用していこうぜ！
と思った人は一度冷静になって考えてみてほしい。
再帰のような破壊的代入を抑えつつループが実現できる手法がありながら、なぜ手続き型言語では極力forやwhileなどを用いるのか？それにはもちろん理由がある。
それは、再帰を使うと、その分スタックメモリが消費されることである。
実は関数呼び出しの際、コールスタックと呼ばれるスタックに関数の情報を格納している。先ほどのorg_sum([1, 2, 3, 4, 5])の例で例えてみると、以下のようになっている。
確かに、リストの要素数が5個であれば、あまり問題はないように思えるかもしれない。だが、100万個近くのデータを扱うとなれば話は別である。
5個で6個の関数の情報をコールスタックに格納しているわけなので、100万個の場合、100万1個の関数の情報をコールスタックに格納することになるだろう。
そしてあまりにも再帰呼び出しが多すぎると最終的にはスタックオーバーフローと呼ばれる、スタックメモリの溢れが生じてしまう。そもそもスタックメモリはそこまで多く格納できるほど容量がなく、コールスタック以外にも使われているため、多くの手続き型言語ではこのような手法はあまりお勧めできない。
末尾再帰
ではすべての再帰が良くないのかと言えば、そうではない。末尾再帰と呼ばれる、関数を再帰的に呼び出すだけの再帰は例外である。
たとえば、以下のようなフィボナッチ関数は、末尾再帰である。
def fib(num, acc=1, cache=1): if num == 0: return 1 elif num == 1: return acc else: return fib((num - 1), (acc + cache), acc)
>>> fib(10) 89
先ほど紹介したorg_sum関数は末尾再帰ではない。なぜなら、自身を呼び出す以外に、リストの0番目の要素を加算しているからである。
return num_list[0] + org_sum(num_list[1:]) ~~~~~~~~~~~ この部分があるため末尾再帰ではない
フィボナッチ関数fibはreturn文によって自身を返すだけとなっているのでこれは末尾再帰となる。
return fib((num - 1), (acc + cache), acc)
以上が末尾再帰である。
それで、末尾再帰だと何が嬉しいのかと言うと、コンパイラによって「末尾呼び出し最適化」と呼ばれる最適化が施されるからである*1。この最適化は、末尾再帰を再帰ではない反復構造に変換してくれるというものであり、スタックメモリを消費しない。
したがって、Haskellを除く、ほとんどの関数型言語はスタックメモリを消費しないという観点から末尾再帰を意識して書くことになる。
Haskellの評価戦略
さて、先ほどHaskellを除くと強調して書いたが、これには理由がある。Haskellの場合は、そもそも末尾再帰であることを意識する必要すらないのである*2。
なぜか。
それはHaskellの評価戦略が関係している。
Haskellは遅延評価（Lazy evaluation）という評価戦略を用いているプログラミング言語の一つである。その反対の、主に手続き型言語で使われている評価戦略は正格評価（Strict evaluation）と呼ばれる。
名前の通り、評価を遅延させる評価戦略なのだが、どのように評価を遅延させるのかと言うと、評価ができない式は後回しにして、評価できるところから評価していく。これによって、正格評価では表現できなかった式を表現できるようになる。
極端な例だと、無限リストがある。GHCiで以下の式を評価してみよう。
ghci> [1..] !! 5 -- 無限リストから5番目の要素を取り出す 6
Haskellで無限リストを表現する場合は[1..]などと書く。これだけで1から順に要素が無限個あるリストを（理論上は）作ることが可能である。そして(!!)はリストの指定した要素を返す関数である*3。(!!)の第二引数に5を適用しており、無限リストの5番目の要素は6であるため、結果は6となる。
このような表現は正格評価では不可能である。
無限リストそのものは最後まで評価できないため、評価を先延ばしにして先に(!!)の第二引数である5を評価する。ここから[1..]の5番目の要素を返すことがわかるので、[1..] !! 5という式は6を返す、というメカニズムとなっている。
遅延評価と再帰
さて、遅延評価によって、Haskellの表現力はかなり豊かであることがわかったであろうと思う。
では、なぜHaskellのような遅延評価だと末尾再帰であることすら気にする必要がないのか。
それは、意外と簡単なことである。実はHaskellにはコールスタックがない。では、スタックメモリを気にしなくて良いのか？と言うと、そうではなくて、Haskellではコールスタックがない代わりにサンクと呼ばれる「まだ評価されていない式」をスタックメモリに格納しているのである。
たとえばHaskellで総和を求める関数を作成する。
sum' :: Num a => [a] -> a sum' [] = 0 sum' (x:xs) = x + sum' xs
ghci> sum' [1..5] 15
まずHaskellではパターンマッチと呼ばれる手法があって、「この関数に何を適用したときどうなるのか」を表現する場合に使われる。
sum' [] = ... sum' (x:xs) = ...
今回のsum'関数の場合、[]（空のリスト）を適用したら0を、空でないリストを適用したらx + sum' xsを返す。
ちなみに(x:xs)もパターンマッチの一種である。これによって0番目の要素xとリストxsを分割することができる。
このパターンマッチによってリストが空になるまでsum'を再帰的に評価している。
では以上を踏まえて、評価した式を展開してみる。
sum' [1..5] = 1 + sum' [2..5] = 1 + (2 + sum' [3..5]) = 1 + (2 + (3 + sum' [4, 5])) = 1 + (2 + (3 + (4 + sum' [5]))) = 1 + (2 + (3 + (4 + (5 + sum' [])))) = 1 + (2 + (3 + (4 + (5 + 0)))) = 1 + (2 + (3 + (4 + 5))) = 1 + (2 + (3 + 9)) = 1 + (2 + 12) = 1 + 14 = 15
このように、Haskellは評価ができるようになるまで評価を先延ばしにする性質がある。そのため、式が先延ばしにされればされるほどどんどんサンクがスタックメモリに格納されていき、最終的にはスタックオーバーフローとなる。
あれ？じゃあ結局末尾再帰にしないといけないのでは？と思われるかもしれないが、これは末尾再帰の場合でも起こる。繰り返しになるが、Haskellは遅延評価によって評価ができるようになるまで評価を先延ばしにするためである。
-- 末尾再帰バージョン sum' :: Num a => [a] -> a sum' (x:xs) = sum'' x xs where sum'' :: Num a => a -> [a] -> a sum'' acc [] = acc sum'' acc (y:ys) = sum'' (acc + y) ys
sum' [1..5] = sum'' 1 [2..5] = sum'' (1 + 2) [3..5] = sum'' ((1 + 2) + 3) [4, 5] = sum'' (((1 + 2) + 3) + 4) [5] = sum'' ((((1 + 2) + 3) + 4) + 5) [] = ((((1 + 2) + 3) + 4) + 5) = (((3 + 3) + 4) + 5) = ((6 + 4) + 5) = (10 + 5) = 15
ではどういう場合なら気にしなくて良いのか？たとえば各要素ごとに関数を適用していったリストを返すmapと呼ばれる関数を独自実装する。
map' :: (a -> b) -> [a] -> [b] map' _ [] = [] map' f (x:xs) = f x : map' f xs
このmap'を使った例は以下のとおりである。
ghci> map' (+3) [1..5] -- 全要素に+3する [4,5,6,7,8] ghci> map' show [1..5] -- 全要素をStringに変換する ["1","2","3","4","5"] ghci> map' (:[]) [1..5] -- 全要素をリストに変換する [[1],[2],[3],[4],[5]]
ちょっと式に示すだけではわかりづらいので図示するとmap'関数は以下のように評価されている。
Haskellは最終的な結果がリストであることがわかっていて、なおかつn+3は評価できる状態なので順番に評価していく。そのため、たとえ第二引数に無限リストを適用したとしても、スタックオーバーフローになることはない*4。
以上から、Haskellで再帰を書く際に気を付けるべきなのは、再帰が末尾再帰であるかというよりも、どのように評価されていくかである。それ以外のほとんどの場合においてHaskellで再帰を書く際あまりスタックメモリ周りを気にする必要はないと思われる。
遅延評価を正格評価に
さて、Haskellでは遅延評価によって普通に再帰を書いても問題ないことがわかった。あとは、遅延評価による評価の引き延ばしをどう対応すれば良いのか、ということである。
実は昔のHaskellではこれに対処する方法がなかったのだが、今では正格評価をするための関数が用意されている。それがseq関数と($!)関数である。
これを使ってフィボナッチ関数を作ってみる。
-- `seq`バージョン fibonacci :: Integral a => a -> a fibonacci n0 = fibonacci' n0 1 1 where fibonacci' :: Integral a => a -> a -> a -> a fibonacci' 0 _ _ = 1 fibonacci' 1 acc _ = acc fibonacci' n acc ca = n `seq` acc `seq` fibonacci' (n - 1) (acc + ca) acc -- ($!)バージョン fibonacci' :: Integral a => a -> a fibonacci' n0 = fibonacci'' n0 1 1 where fibonacci'' :: Integral a => a -> a -> a -> a fibonacci'' 0 _ _ = 1 fibonacci'' 1 acc _ = acc fibonacci'' n acc ca = ((fibonacci'' $! (n - 1)) $! (acc + ca)) acc
ghci> fibonacci 10 89 ghci> fibonacci' 10 89
fibonacci 10の式を展開してみる。
fibonacci 10 = fibonacci' 10 1 1 = fibonacci' (10 - 1) (1 + 1) 1 = fibonacci' 9 2 1 = fibonacci' (9 - 1) (2 + 1) 2 = fibonacci' 8 3 2 = fibonacci' (8 - 1) (3 + 2) 3 = fibonacci' 7 5 3 = fibonacci' (7 - 1) (5 + 3) 5 = fibonacci' 6 8 5 = fibonacci' (6 - 1) (8 + 5) 8 = fibonacci' 5 13 8 = fibonacci' (5 - 1) (13 + 8) 13 = fibonacci' 4 21 13 = fibonacci' (4 - 1) (21 + 13) 21 = fibonacci' 3 34 21 = fibonacci' (3 - 1) (34 + 21) 34 = fibonacci' 2 55 34 = fibonacci' (2 - 1) (55 + 34) 55 = fibonacci' 1 89 55 = 89
遅延評価の場合は、再帰が終わるまで四則演算を後回ししていたために、最悪の場合スタックオーバーフローしていた。しかし、seq関数もしくは($!)関数を使うことで先に評価しておくべき式を逐次評価するようになった。
このように今のHaskellでは遅延評価によってスタックオーバーフローしてしまうような関数はseq関数もしくは($!)関数を使い正格評価にすることが可能である。
おまけ: foldlを使うのはやめよう
Haskellにはfoldlという関数がある。これはHaskellで畳み込みを実現するために使われる関数なのだが、実はこの関数には遅延評価によってスタックオーバーフローが起こってしまうという問題がある。
その問題を解決した関数がfoldl'である。Data.Listモジュールをインポートすることで使うことができるので、もしfoldlを使って関数を作りたいのであれば、foldl'を使うべきである。
補足記事書きました
参考
- すごいHaskellたのしく学ぼう!
- Stack overflow - HaskellWiki
