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
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
