評価戦略（簡約戦略）でいつか書くべきことのメモ
さざんかぬふ元々は、関数型プログラミングのメリットみたいなこと...
いわゆる純粋関数だけでプログラムが書かれている場合、評価戦略によらず（評価が止まるのであれば）その止まる評価は一致するという事がある。
でも、その評価までに必要な式変形なり基本操作なりの数は評価戦略によって大きく変わる場合があるので、必ずしも正格でない、基本操作が少なくて済む評価戦略を選べると、計算がとても早くなる可能性はある。
無限リストをfoldrで扱うとかも、ある意味ではそういうことで、無限リストを素朴な正格評価で扱おうとするといつまでも計算が止まらない...
例えばフィボナッチ数列F_nがあるとき、F_5の計算を、F_nすべてを求めてからF_5を計算するみたいな事にすると計算が終わらない。有限で打ち切ってF_100まですべて計算してからF_5を得るとかにしても、無駄な時間がかかる。けど、F_5だけを計算するとそれでよい。
これは、mapの計算にfilterを入れる場合とかに通じることで、filterして取得される件数が1件のとき、評価順序が任意であればすべてのmapを行う前にfilterするという事が可能になるため、filterした後にmapすると計算量滅茶苦茶減るといえば減る
※filterがmapの結果に依存する形だと、mapの計算が必要になるけど、無条件に先頭とか最後とかを取っているのであれば、さきに先頭とか最後を取ってからmapの関数を適用すればよくなるということ。手続き的な書き方では、この適用順序を意識しないといけないけど、評価戦略を自動で良い感じに考えてくれる言語であれば、それを人間が考えなくて良い、あるいはわかりやすい書き方をしておいても勝手に最適化してくれる。
＜非正格の評価について＞
mapを複数回適用するときに、f.g.h みたいな合成関数を先に計算してからmapを適用するのと同じ事を勝手にしてくれる、みたいな利点はあるとは思うけど、なかなかむずかしいよね（雑に書くとループ回数が増えるやつ）
極端な場合、f.g.hがidとかだと計算量はほぼゼロになる（可能性がある）
（f.gがidになる例だけど）
1足すという関数をadd1
1引くという関数をsub1
と書くと、関数適用せずに、
add1.sub1 = id
ということを示せる場合がある（これは個々の要素の計算じゃなくて、関数としての計算によって）
そうすると、add1.sub1(x)はもはやid(x)なので計算せずにxとわかる。
これが極端な場合で、一般に関数と関数から別の関数を作るという演算を、関数適用せずに行ってしまうと高速になり得るという話
まあ評価戦略の影響が現実の場面でどれぐらいというと、私個人の携わる範囲ではmapとかfilterぐらいかなと思うけど、たらい回し関数（竹内関数）みたいなものがある
＜証明について＞
あと、別のアプローチで証明という事もあって、例えばフィボナッチ数列において
F_n=F_{n-1}+F_{n-2}=2F_{n-2}+F_{n-3}
なんだけど、これをテストで代表値だけで示すのではなくて、代数的な式として証明するという事もできる。これも純粋関数の強み。
ちなみに、
F_n=F_i *F_{n-i}+F_{i-1}*F_{n-i-1}
なんだけど、これも証明できる（代表値によるテストではなく）
さざんかぬふ参考（といってもこれを書くのに参考にしたわけではないが）
※日本のRubyコミュニティとは？みたいな微妙な記述はあるが
さざんかぬふ無限リストの計算を非正格評価ではやくできるというような話は、数学的には実は中学〜大学で当たり前にやられている事でもある。
たとえば、f(x) = x^2という関数とg(x) = 2*x + 1があったときに、
h(x) = f(x) + g(x) = x^2 + 2x + 1 = (x+1)^2
という計算をするのは、ある種の非正格評価になっている（xの具体的な値に依存しない、関数と関数から関数を返す演算なので）
無限リストは、a_0, a_1, a_2, ...という数列とも思えるので、自然数をドメインとする関数とみなせて、無限リストの個々の要素の計算をせずに計算方法だけを計算するというのは、いわゆる代数的な手続きと等価になっている。
人間が手計算をする場合というのは、こうした評価戦略みたいなもののうち適当に都合がよいものを選んで、良い感じの結果を得るという手続きと思える。昔のコンピュータ（？）は与えられた順序で単純な計算をすることしかできなかったけど、研究が進むにつれて、例えば無限リストであっても個々の値を計算せずにある意味で人間と"同じように"計算をするという手法が生まれた。
さざんかぬふ私がこの辺の話でよく感じるのは、無限級数の足し算とか引き算みたいな事であったり、ある数を無限級数として表したり一文字で表したりみたいなこと。
1/(1-x) = 1 + x + x^2 + ...
という式があったとき、左の書き方は項が一つだけど、右の書き方は項が無限にある。こういう無限の項を素朴にすべて表現しようとすると、愚地独歩みたいな大変な/意味不明なことになってしまうけど、扱いにくい無限みたいなものを適当に有限の文字で表現しておけば（この場合は1 + x + x^2 + ...という有限の文字列）、いい感じの計算方法が見つかったときにうまく計算ができる。
イメージ的にはくりこみみたいな事も近いんだけど、イメージでしかない...
