トップ «前の日記(2008-11-15) 最新 次の日記(2008-11-20)» 月表示 編集

日々の流転


2008-11-17 [長年日記]

λ. Arrays without bounds

Haskellの普通の配列はサイズを指定して作るので、リストと違って無限の長さを持つ配列は作れないのだけど、こいつは無限の長さの配列を実現したものだそうだ。 実装はとてもシンプル。メモ化とかに便利。

ただ、内部の各リサイズでサイズが幾何的にしか増えないというだけでは、要素アクセスの償却計算量が O(1) であることは保証出来ないような。 というのも、配列はランダムアクセスされるので、十分な「引当」が行われる前に次のリサイズが起こりえると思うので。

Tags: haskell