2008-11-17 [長年日記]
λ. Arrays without bounds
Haskellの普通の配列はサイズを指定して作るので、リストと違って無限の長さを持つ配列は作れないのだけど、こいつは無限の長さの配列を実現したものだそうだ。 実装はとてもシンプル。メモ化とかに便利。
ただ、内部の各リサイズでサイズが幾何的にしか増えないというだけでは、要素アクセスの償却計算量が O(1) であることは保証出来ないような。 というのも、配列はランダムアクセスされるので、十分な「引当」が行われる前に次のリサイズが起こりえると思うので。
[ツッコミを入れる]
