Hashtable ADT

[John Hughes]

	> 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