さらに遊んでみる

上記の配列は、そのままでは破壊的代入出来ないので、そういう関数を定義してみる。

let replace array x y z =
	if x = z then y else array z;;
let array2 = replace array1 3 10;;

書き換えのオーダーは0だけれども、参照するためのオーダーはもはや不定。参照するための時間が書き換えの回数に比例するような配列書き換え(すでに配列とは言わないが)。
で、ここから何を考えたかと言えば、この擬似配列はつい最近書き換えたものに関しては非常に高速に値を返すというスタック構造になっていることが自明に分かる。ということは、前半の値はどうでもよいようなケースであれば、普通に記述するよりも綺麗に書けるのではないだろうか。
例えばフィボナッチ数列のn項を出すプログラムの場合、最悪なアルゴリズムはO(n^2)かかってしまう。だが、ちょっとましなアルゴリズムならばO(n)となる。さすがにO(log n)にまで落とすのは無理かもしれないが、この方針でO(n)が自然に記述できないだろうか。
と思ったのですが、普通に配列を使った方が綺麗にかけるので、省略します。相当めんどくさかったのですが、消去。