Gabi, If the structure is simple enough that it can be represented using arrays, or if you write it in IO using IORefs, you can do it, but idiomatic Haskell generally can't perform as well for the problem you describe as a language that updates in place. Even so, overall the compiler optimizes very well. Haskell is such a good language that you may be able to achieve the performance you want with IORefs (IORefs are _very_ fast), and even though it's not as pleasing as Haskell code can be, the code may still be better than you could do in an imperative language, but this would depend a bit on the details of your problem. Gabi wrote:

Maybe Data.Sequence is a good option. Seems to be designed to give good performance when mutating If trees could be represented using Data.Sequence, I think that tree manipulation performance would be bearable. Any other libraries that might be useful?

I use Data.IntMap a lot, including a wrapped version that takes any Enum as a key (which I intend to put on Hackage some time). Data.IntMap, Data.Map and Data.Sequence are a bit slower than update-in-place languages, but algorithmically they're very good and the performance is definitely not terrible. You might be interested in taking a look at http://haskell.org/haskellwiki/DDC. Disciple is a Haskell-like language - with the project being at a very early stage - that includes mutability in its type system so you can mutate state in place, but with the same strong guarantees of purity that you get in Haskell with the ST and State monads. The compiler is incomplete but it does work for the core of the language, so it's possible to write small programs in it. Steve Gabi wrote:

I might be wrong but I think this is a weak spot for many functional langs, including Haskell - The ability to manipulate in high rate data structures without killing the performance . Even in langs like Clojure, which enable the cheap creation of new modified structures out of old ones(using "persistent structures") -it is much slower than using an imperative language to manipulate data in place. What is the approach of Haskell to this ?