Question: I am looking for a mutable (balanced) tree/map/hash table in Haskell or a way how to simulate it inside a function. I.e. when I call the same function several times, the structure is preserved. So far I have tried Data.HashTable (which is OK, but somewhat slow) and tried Data.Array.Judy but I was unable to make it work with GHC 6.10.4. Are there any other options?

Answer: 
Although you ask for a mutable type, let me suggest that you use an immutable data structure and that you pass successive versions to your functions as an argument.

Regarding which data structure to use,

* There is an [implementation of red-black trees](http://www.cs.kent.ac.uk/people/staff/smk/redblack/rb.html) at Kent
* If you have integer keys, `Data.IntMap` is extremely efficient.
* If you have string keys, the [`bytestring-trie` package from Hackage](http://hackage.haskell.org/package/bytestring-trie) looks very good.

> 
> The problem is that I cannot use (or I don't know how to) use a non-mutable type.
> 
> 
> 

If you're lucky, you can pass your table data structure as an extra parameter to every function that needs it. If, however, your table needs to be widely distributed, you may wish to use a [state monad](http://www.haskell.org/all_about_monads/html/statemonad.html) where the state is the contents of your table.

If you are trying to memoize, you can try some of the lazy memoization tricks from Conal Elliott's blog, but as soon as you go beyond integer arguments, lazy memoization becomes very murky—not something I would recommend you try as a beginner. Maybe you can post a question about the broader problem you are trying to solve? Often with Haskell and mutability the issue is how to contain the mutation or updates within some kind of scope.

It's not so easy learning to program without any global mutable variables.
> 
> Are there any other options?
> 
> 
> 

A mutable reference to a purely functional dictionary like `Data.Map`.