09/10/05 21:38:23
>>929
ハッシュテーブルの検索は O(1) でできるのが特徴だと思います（最悪ケースでO(n)）。
一方 Prelude の lookup 関数の実装は O(n) です。
なので、それはハッシュとは言えないのではないでしょうか。
Data.HashTable.Lookup の実装が O(n) になっていたら、
GHC のウソつきということになりますが。
09/10/05 21:38:23
>>929
ハッシュテーブルの検索は O(1) でできるのが特徴だと思います（最悪ケースでO(n)）。
一方 Prelude の lookup 関数の実装は O(n) です。
なので、それはハッシュとは言えないのではないでしょうか。
Data.HashTable.Lookup の実装が O(n) になっていたら、
GHC のウソつきということになりますが。