>>707
解説ありがとうございます
やはりメモ化するしかないんだと思います
問題はそれがプログラマが明示的に自分でやらないといけないのか、コンパイラが自分でやってくれるのかの差なんだと思います
Haskellは純粋なcall by nameではなく、call by needのシステムの中にメモ化を備えていてプログラマがメモ化するように書いてなくても勝手にメモ化できるものをメモ化してくれるのがすごいとこだと思うんですけど、例えば>>703の2番目の例で最初見た時「なんでこの定義式でメモ化が効くんだ？」とさっぱりわからなかったのが、実はHaskellのcall by needのシステムをうまく利用してるらしいとわかったのが最初なんです
で二重の漸化式だとうまくいかないなと
もちろん二重の全炊きでも上手くsuffixの取り方を変えたりすると同様の方法でメモ化できるんですけど、それでは結局「Haskellの機能を利用して明示的にメモ化を指定することなく高速化した」事にはなりません
まぁコレはしょうがないんでしょうね
どんな計算も常にメモ化して常に同じ評価式を2度扱う事を防いでたらそんなの逆に使い物になりませんからね