[Haskell-beginners] Fast tree manipulation
Stephen Blackheath [to Haskell-Beginners]
mutilating.cauliflowers.stephen at blacksapphire.com
Wed Feb 3 15:08:40 EST 2010
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.
> 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.
> 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 ?
More information about the Beginners