[Haskell-beginners] Fast tree manipulation

[Stephen Blackheath [to Haskell-Beginners]]

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 ?
>