Quote:
Originally Posted by Loriel
I have never felt a stronger urge to throw my chair at some guy through the internet than I am experiencing right now. 
I would not even know where to begin to write an associate array in haskell that has any better than O(n) lookups. |
Haskell provides the
lookup function which works differently on different data structures.
If you do it on a list like [("a", "1"), ("b", "2"), ("c", "3")] it'll return in O(n).
However, if you do it on a Data.Map which are represented as immutable balanced binary trees, it'll give you a O(log(n)).
Those would be the preferred methods since they both provide a purely functional interface, but you can use hash tables as well with an imperative interface in the IO Monad (with a data HashTable) giving you the O(1).