6

私はいくつかのコードを書いていて、タプルの無限リストから無限マップを作成できると考えました。次の行に沿ったもの: Map.fromList [(i,i+1)|i<-[1..]]

もちろん、Data.Map と Data.Set はそれぞれ無限のマップとセットをサポートしていないことがすぐにわかりました。の Data.Set の貪欲な実装に関する同様の質問に気付きました。ここfromListでの回答を読んだ後、Set では怠惰な実装と貪欲な実装の両方が可能であることは明らかですが、貪欲な実装の方がうまく機能します。ただし、遅延実装が機能しない理由はよくわかりません。鍵の保管方法と関係がありますか?Map.fromList

4

1 に答える 1

13

Data.Mapバランスの取れたツリーとして実装されます(ほぼバイナリだと思います)。入力についての事前の知識がなければ、無限の二分木を怠惰に作成してバランスを取るのは困難です。ただし、代わりに(ビットの)遅延無限試行を使用するMemoTrieパッケージのようなものが好きかもしれません。

> let x = trie (\x -> x+1)
> untrie x 72
73
> untrie x 37
38
于 2012-04-21T19:44:35.370 に答える