[Haskell-cafe] symbol type?

[jerzy.karczmarczuk at info.unicaen.fr]

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