プログラミング Haskell 第 2 版 †
 | プログラミングHaskell 第2版 Grahum Hutton ラムダノート 2019-08-02 ￥ 3,456 |
第7章 高階関数 †
p.82
蓄積変数 †
「蓄積変数」とは、「accumulator」のこと。
- 再帰ドリル(2)：数値に対する末尾再帰 - あどけない話
素朴な再帰を「末尾再帰」(tail recursion)という形に直すと、スタックが溢れなくなる。
末尾再帰の形をした関数とは、分岐の末端の最後で自分自身を呼び出す関数のことである。
ループできることを実装している再帰関数は、「引数を増やすことで末尾再帰に直せる」。
増やされた引数は「蓄積変数」(accumulator)と呼ばれる。
蓄積変数に結果を蓄えていき、最後にそれを返す訳だ。
関数型言語を名乗るプログラミング言語であれば、再帰の末尾呼び出しは、単なるジャンプ(goto)に置き換えられるので、スタックは溢れない。
これを「末尾呼び出しの最適化」(TCO: tail call optimization)と言う。
foldl（fold left） †
プレリュードで提供される高階関数 foldl（fold left の略称）は、演算子 #と蓄積変数 vを引数としてこの再帰の様式を閉じ込めたものです。
関数 foldl自体は再帰を用いて定義できます。
foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v [] = v foldl f v (x:xs) = foldl f (f v x) xs
p.83
7.5 関数合成演算子 †
プレリュードで提供される「(.)」は、二つの関数を合成した関数を返す高階演算子です。
この演算子は以下のように定義できます。
(.) :: (b -> c) -> (a -> b) -> (a -> c) f . g = \x -> f (g x)
関数合成のが結合則 †
適切な型を持つ任意の関数 f、g、hに対し、f . (g . h) = (f . g) .hが成り立ちます。
- ［訳注］英語では “f composed with g” と読みます。「gと合成された f」という意味です。
- ［訳注］演算子 .で合成できるのは、引数の個数が一つの関数のみです。
このため、適用範囲が狭いと思うかもしれません。
しかし、Haskell では部分適用を用いることによって、関数が取る引数の数を一つにできます。
部分適用した関数を合成する例が直後に示されていることに注意しましょう。 - ［訳注］関数合成を用いて関数を定義する形式をポイントフリースタイルと呼びます。
ポイントとは値のことです。
つまり、引数を用いない形式という意味です。
