[Haskell-cafe] Re: symbol type?

2007-10-10 Thread apfelmus 

Michael Vanier wrote:

Yitzchak Gale wrote:

Ah. Perhaps Data.HashTable is what you are looking
for then?


Hmm, I was hoping for something that didn't involve side effects.


There's always Data.Map

  newtype Symbol   = S { unS :: Integer } deriving (Eq, Ord)
  type SymbolTable = Data.Map Symbol String

Regards,
apfelmus

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: symbol type?

2007-10-10 Thread Yitzchak Gale 
I wrote:
 Perhaps Data.HashTable is what you are looking
 for then?

Jerzy Karczmarczuk wrote:
 extract from Data.Hash what you need...
 why not try tries?

apfelmus wrote:
 There's always Data.Map

Those are log n. I would personally use those for
almost every application, but Mike says he wants
constant time, for a compiler. Apparantly he wants
to do some really serious optimization. HashTable
is highly optimized.

Of course, any memory access is really no better
than log n, but HashTable uses the built-in parallelization
available on most hardware that makes it look like
constant time up to the size of system memory.
(Otherwise known as accessing memory locations
by address.) So yes, using this hardware has side
effects and needs to be in IO.

You could do it in the ST monad instead of the IO
monad if you want, if that is any consolation.

-Yitzchak

-Yitz
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: symbol type?

2007-10-10 Thread Philippa Cowderoy 
On Wed, 10 Oct 2007, Yitzchak Gale wrote:

 I wrote:
  Perhaps Data.HashTable is what you are looking
  for then?
 
 Jerzy Karczmarczuk wrote:
  extract from Data.Hash what you need...
  why not try tries?
 
 apfelmus wrote:
  There's always Data.Map
 
 Those are log n. I would personally use those for
 almost every application, but Mike says he wants
 constant time, for a compiler.

However, I'm guessing he can use key comparison rather than value 
comparison - that changes things somewhat.

-- 
[EMAIL PROTECTED]

My religion says so explains your beliefs. But it doesn't explain
why I should hold them as well, let alone be restricted by them.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe