![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
#html{{
table border="0" cellpadding="5"><tr><td valign="top"><a href="https://www.amazon.co.jp/exec/obidos/ASIN/4908686076/vertex9-22/" target="_blank"><img src="
" border="0"></a></td><td> </td><td valign="top"><a href="https://www.amazon.co.jp/exec/obidos/ASIN/4908686076/vertex9-22/" target="_blank">プログラミングHaskell 第2版</a><br>Grahum Hutton<br>ラムダノート<br>2019-08-02<br>￥ 3,456</td></tr></table>
}}
p.82
「蓄積変数」とは、「accumulator」のこと。
素朴な再帰を「末尾再帰」(tail recursion)という形に直すと、スタックが溢れなくなる。
末尾再帰の形をした関数とは、分岐の末端の最後で自分自身を呼び出す関数のことである。
ループできることを実装している再帰関数は、「引数を増やすことで末尾再帰に直せる」。
増やされた引数は「蓄積変数」(accumulator)と呼ばれる。
蓄積変数に結果を蓄えていき、最後にそれを返す訳だ。
関数型言語を名乗るプログラミング言語であれば、再帰の末尾呼び出しは、単なるジャンプ(goto)に置き換えられるので、スタックは溢れない。
これを「末尾呼び出しの最適化」(TCO: tail call optimization)と言う。
プレリュードで提供される高階関数 foldl（fold left の略称）は、演算子 #と蓄積変数 vを引数としてこの再帰の様式を閉じ込めたものです。
関数 foldl自体は再帰を用いて定義できます。
#code(haskell){{
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs
}}
p.83
プレリュードで提供される「(.)」は、二つの関数を合成した関数を返す高階演算子です。
この演算子は以下のように定義できます。
#code(haskell){{
(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)
}}
適切な型を持つ任意の関数 f、g、hに対し、f . (g . h) = (f . g) .hが成り立ちます。
