> As I understand from the concepts of Functional Programming, it is not > possible to implement a Hashtable ADT in Haskell language, where one can > insert, and access values in O(1) complexity. It has to be implemented > with an external language. I don't know if it can be done in standard Haskell 98, but it can certainly be done using extensions provided by most or all implementations (IORef, IOArray). There is no need of using an external language, although it will not fit well the functional style. Better is to use the ST monad (which provides creation, reading, and writing of arrays and references in constant time). Side-effects in the ST monad can be encapsulated using runST :: (forall s. ST s a) -> a You give it a computation using updateable state as an argument, a "state thread", and it gives you the result as a pure value. The "forall s" is a typing trick which prevents an encapsulated state thread from referring to references belonging to a different state thread. Using this you can, for example, create a function share :: Hashable a => [a] -> [a] which takes a list of hashable values, and returns an equal list, in which equal values are always represented by the same pointer. Internally, there's a hash table which lets you map each element of the input to a unique representative. You could compose share with a lexical analyser, for example, to share all the copies of the same identifier. Encapsulated stateful operations like this fit very nicely with the functional style! Take a look at "State in Haskell", John Launchbury and Simon Peyton Jones, http://www.cse.ogi.edu/~jl/Papers/stateThreads.ps which explains all of this at length. John Hughes