アルゴリズムの代表っぽい存在とも言えるDPですが,Haskellは参照透明なので書きにくいと思われがちです. しかし,実際は,C言語やSTLなしのC++より遥かに簡単に動的計画法が書けます. リストを用いる 最初に知るであろう方法. フィボナッチ数列の第100項だと, let f = 0 : 1 : zipWith (+) a (tail a) in f!!100 です. 「ずらして足したものを後ろにつなげる」と言えばいいのでしょうか. これについては,他でよく解説されているので詳しくは説明しません. 利点: リストの知識のみでよい. 無限リストの恩恵が受けられる. importが不要. 欠点: 使えるケースが限られる. 書くときに,混乱することも(上の例だと,と考える必要がある. ランダムアクセスができないので,場合によってはO(n)倍の時間がかかる*1. 添字を自由に用いることができな