遅延評価 - lethevert is a programmer

最近連続している遅延評価を考えるシリーズです。
昨日の話とは、別の角度から、考えてみました。
[id:lethevert:20051124:p2]で挙げたソース、

...
where
    calcs = getCalc
    where
        getCalc = [calc x \\ x <- [0..]]

という無限リストが使えないという話です。いや、使えるように使えば、使えるものなのですが、最初に期待したほどには使えないということなんです。

リストのアクセスのオーバーヘッド

計算結果にアクセスする際に、連続アクセス（順次アクセスなど）なら問題ないのですが、ランダムアクセスになると、リストのアクセスコストのオーバーヘッドがかかって、効率的なキャッシュにならないのです。
ところで、この無限リストを使ったキャッシュって、memoizeのことを書いたときに使っていました。
[id:lethevert:20050904:p3]
このソースは、リストのアクセスがランダムアクセスになっているため、アクセスコストがかかって、効率的なキャッシュになっていません。しかし、フィボナッチ数列は順次アクセスにできるので、この関数はもっと効率よく定義することは可能です。
ところで、何故リストだとアクセスコストがかかるかというと、Concurrent Cleanのリスト（Haskellのリストも同じ）は、Linked Listであるため、アクセスするには、頭から順番に連結をたどって行かなければならず、インデックスが１つ増えるごとに、メモリアクセスの回数が１つ増えてしまうからです。

配列は使えないの？

さて、ランダムアクセスに適した配列を使えば、効率のよいキャッシュになるのではないかと思って、

...
where
    calcs = getCalc
    where
        getCalc = {calc x \\ x <-: {0..}}

このように書き換えてみたとしても、これは無理です。
なぜなら、配列は、あらかじめ要素の個数分だけメモリを確保しておかなければいけないのですが、無限要素の配列を作成するには、無限のメモリが必要になるわけで、それは現実的に不可能です。

そもそもなぜ無限リストが可能なのか？

リストというのは、その見た目や直感的な概念像とは異なり、再帰的なデータ構造であって、再帰的なデータ構造と遅延評価が組み合わさって、無限リストが定義できているのです。
無限リストは、このように書いたのと同じことです。

//事前定義
::List a = List a (List a)
InfList x = List x (InfList (x+1))

//[0..]と同じもの
fromZero = InfList 0

これを見ると、昨日のWebと構造がよく似ていることが分かります。

::Web = Web WebPage [Web]
getWeb page
    = WebPage page (map getWeb pages)
where
    pages = getLinkedPages page

どういうデータ構造が定義できるとよいのか？

概念上無限の要素（で、実際には有限の要素）に対して、インデックス（キー）によるランダムアクセスができるようなデータ構造といえば・・・
~~ハッシュ~~ マップ（ディクショナリ）が、遅延評価を有効にして、宣言的に定義できるとこの辺の問題はかなり解決しそうです。
たとえば、~~ハッシュ~~ マップをこんな感じ（↓）の書式で書くとして、リストのような内包表記ができるとします。

::Map key val
    = #< key __ val >

すると、こんな感じに書いてやれば、効率のよいキャッシュが作成できそうです。

...
where
    calcs = getCalc
    where
        getCalc :: Map Int Real
        getCalc = #< x __ calc x \\ x <- any >

ついでに、~~ハッシュ~~ マップなら、キーがIntに限定されないというメリットもありそうです。
さて、これは、実現可能なのか？あるいは、既に誰かが実装済みなのか？

（追記）
ハッシュをマップに書き換えました。というのは、上の議論は、ハッシュという実装には依存していなくて、キーで高速にランダムアクセスできるインターフェースがあればよいだけだからです。