##再帰で本当に大丈夫?
Haskellは、ループ処理を「言語構文としては」サポートしていません。
「ループは再帰で書くのが関数型言語」とか良く言われます。
でも、手続き型言語の世界から来た人にとっては「再帰って、スタック膨れるんじゃね?」って、不安に思いますよね?
あなたの心配は正しい!
Haskellだって、うっかりな再帰をすればStack space overflowを起こします。
そうならないために、どのような再帰を書くべきか/書かないべきかを知っておきましょう。
##整数リストの和 標準で存在するsum関数を、自前で実装してみます。
sum' [] = 0
sum' (x:xs) = x + sum' xs関数sum'に、リスト[1, 2, 3]を与えると、下記のように評価されます。
sum' [1, 2, 3] = 1 + sum' [2, 3]
= 1 + (2 + sum' [3])
= 1 + (2 + (3 + sum' []))
= 1 + (2 + (3 + 0))
= 6再帰的な呼び出しになっていますが、再帰呼び出し完了後に(+)演算子の評価を行うため、再帰呼び出し完了後の戻り先をスタックに積む必要があります。 長いリストが渡されて再帰が深くなると、それだけスタックが膨れ上がることになります。
##末尾再帰
関数型言語が、ループを再帰で実現するするための重要な仕組みが「末尾呼び出し最適化」です。
これは、「関数の末尾が関数呼び出しで終わる場合、その呼び出しをジャンプに置き換える」というものです。戻り先をスタックに積む必要がなくなるため、スタックが膨れ上がることを防ぐことができます。
末尾の関数呼び出しが再帰である場合、特に「末尾再帰」と呼びます。末尾再帰はループと等価です。
つまり、関数型言語でループを実現するには末尾再帰にする必要があります。
##末尾再帰に書き換える
ということで、スタックが溢れないように、関数sum'を末尾再帰の形に書き換えます。
sum'' as = iter as 0
where
iter [] acc = acc
iter (x:xs) acc = iter xs (acc + x)末尾再帰に書き換える際のテクニックの1つとして、上記accのように計算結果を積み上げる引数を追加する方法があります。 このような変数のことを「アキュムレータ」と呼びます。
関数sum''に、リスト[1, 2, 3]を与えると、下記のように評価されます。
sum'' [1, 2, 3] = iter [1, 2, 3] 0
= iter [2, 3] (0 + 1)
= iter [3] ((0 + 1) + 2)
= iter [] (((0 + 1) + 2) + 3)
= 6関数iterの末尾再帰になっているので、実際はループと同じコードに変換されます。
※なお、今回はサンクについての議論を端折っています。実際は、上記のままでは、サンクが膨れ上がってやっぱりStack space overflowとなってしまいます。そのあたりの事情は第6章で…
##末尾再帰が良いとは限らない
では、何でもかんでも末尾再帰にすべきかと言えば、そうでもありません。
例えば、Intリストを受け取り、各要素に1を加算したリストを返すincListを末尾再帰で定義すると、下記のようになります。
incList as = iter as []
where
iter [] acc = acc
iter (x:xs) acc = iter xs (acc ++ [x + 1])関数incListに、リスト[1, 2, 3]を与えると、下記のように評価されます。
incList [1, 2, 3] = iter [1, 2, 3] []
= iter [2, 3] [2]
= iter [3] [2, 3]
= iter [] [2, 3, 4]
= [2, 3, 4]一見問題無さそうですが、答えを返すために、渡されたリストの要素全てを評価しています。
これは、無限リストが渡された場合に停止しないことを意味します。
一方、末尾再帰でない形で定義した場合は、下記のようになります。
incList' [] = []
incList' (x:xs) = (x + 1) : incList' xs関数incList'に、リスト[1, 2, 3]を与えると、下記のように評価されます。
incList' [1, 2, 3] = 2 : incList' [2, 3]
= 2 : (3 : incList' [3])
= 2 : (3 : (4 : incList' []))
= 2 : (3 : (4 : []))
= [2, 3, 4]例えば、関数takeと組み合わせた場合、無限リストを与えても、遅延評価のおかげで下記のように評価され停止します。
(take 2) (incList' [1..]) = (take 2) (2 : incList' [2..])
= (take 2) (2 : (3 : incList' [3..]))
= [2, 3]なお、sum'の場合と違うのは、sum'の結果はリストの総和なので、リストの全要素を評価しないと決定できません。 一方incList'の場合は、先頭から必要な要素だけを評価し、不要な部分の評価を省略しています。
通常は、与えられたリストと同順の結果のリストを返す場合は、末尾再帰で無い方が良いです。
##畳み込み
sum''の例であった
sum'' [1, 2, 3] = (((0 + 1) + 2) + 3)のアキュムレータの初期値を引数で与えられるようにすると
sum'' [1, 2, 3] acc = (((acc + 1) + 2) + 3)という風に、アキュムレータに対して、リストの左要素から足しこんでいく操作になります。
一般的に、リスト[E1, E2, E3, ..]とアキュムレータaccと2引数関数fがある場合、
(f (f (f acc E1) E2) E3) ..とする操作を「左畳み込み」と呼びます。
一方、incList'はアキュムレータを用いて
incList'' as = iter as []
where
iter [] acc = acc
iter (x:xs) acc = (x + 1) : iter xs accと書き換えられます。sum''の場合と同様に、アキュムレータの初期値を引数で与えられるようにすると
incList'' [1, 2, 3] acc = 2 : (3 : (4 : acc))という風に、アキュムレータに対して、リストの右要素から足しこんでいく操作になります。
一般的に、リスト[.., En-2, En-1, En]とアキュムレータaccと2引数関数fがある場合、
.. (f En-2 (f En-1 (f En acc)))とする操作を「右畳み込み」と呼びます。
左畳み込みは、メモリを節約した再帰を実現できます。
一方、右畳み込みは、リストの要素の評価を省略可能な再帰を実現できます(省略可能なので、無限リストも扱える)。
畳み込みについては、関数foldl/foldrとして、第5章で登場します。