I'm looking for a monad-free, constant access query O(1) associative array.
Consider the hypothetical type:
data HT k v = ???
I want to construct an immutable structure once:
fromList :: Foldable t, Hashable k => t (k,v) -> HT k v
I want to subsequently query it repeatedly with constant time access::
lookup :: Hashable k => HT k v -> k -> Maybe v
There appears to be two candidate libraries which fall short:
unordered-containers
hashtables
unordered-containers
unordered-containers
contains both strict and lazy variants of the type HashMap
. Both HashMap
s have O(log n) queries as documented by the lookup
function. This query access time appears to be due to the construction of the HashMap
types, which have an internal tree structure allowing for O(log n) insert
functionality. An understandable design trade off for many use-cases, but since I don't need a mutable HashMap
this tradeoff hampers my use-case.
hashtables
hashtables
contains a HashTable
type-class and three instance types with varying table constructions strategies. This library's type-class defines a constant time O(1) lookup
function definition, but it is eternally embedded in the ST
monad. There is no way to "freeze" the stateful HashTable
implementations and have a lookup
function that is not embedded of a stateful monad. The library's type-class interface is well designed when the entire computation is wrapped in a state monad, but this design is unsuitable for my use-case.
Does there exist some other library which defines types and functions which can construct an immutable constant access query O(1) associative array that is not embedded in a stateful monad?
Does there exist some way to wrap or modify these existing hashing-based libraries to produce an immutable constant access query O(1) associative array that is not embedded in a stateful monad?
A dictionary (also known as a map, hashmap or associative array) is a set of key/value pairs.
Hash tables or has maps in Python are implemented through the built-in dictionary data type. The keys of a dictionary in Python are generated by a hashing function. The elements of a dictionary are not ordered and they can be changed.
The library you want is… unordered-containers
. Or just plain old Data.Map
from containers
, if you’d prefer.
The note in the unordered-containers
documentation explains why you shouldn’t worry about the O(log n) time complexity for lookups:
Many operations have a average-case complexity of O(log n). The implementation uses a large base (i.e. 16) so in practice these operations are constant time.
This is a common practice with certain kinds of functional data structures because it allows good sharing properties while also having good time complexities. log16 still produces very small numbers even for very large n, so you can almost always treat those complexities as “effectively constant time”.
If this is ever a bottleneck for your application, sure, go with something else, but I find that highly unlikely. After all, log16(1,000,000) is a little under 5, so your lookup time is not going to grow very quickly. Processing all that data is going to take up much more time than the overhead of the lookup.
As always: profile first. If you somehow have a problem that absolutely needs the fastest possible hash map in the world, you might need an imperative hash map, but for every case I’ve ever had, the functional ones work just fine.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With