
Michael Vanier, before Yitzchak Gale and himself:
I'm thinking of a symbol type that can be used for a compiler...
Ah. Perhaps Data.HashTable is what you are looking for then?
Hmm, I was hoping for something that didn't involve side effects.
Some popular Haskell libraries suffer from acute Monaditis. The hash tables, the random numbers, etc., all is embedded in IO or something similar. But the essential algorithms are independent of this structuration. You *can* make streams of random numbers, using the same generation algorithms, without monads. You *can* make your hashed sequences of strings using lists, without monads. You will be simply obliged to carry with you all that stuff, as *explicit* world state. So, go ahead, extract from Data.Hash what you need, and structure the access and the eventual insertions/deletions in a way you wish. The basic idea of constant-time access strings is usually based on hashing. But you may wish to be more elegant... So, why not try tries? http://en.wikipedia.org/wiki/Trie http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node22.html http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Trie/ They have been implemented in Haskell as well, probably many, many times. But beware, Google on "Haskell tries" will offer you this: http://www.muskogeephoenix.com/highschoolsports/local_story_281003617.html Jerzy Karczmarczuk