[Haskell-cafe] Optimizing hash array mapped tries

[Edward Z. Yang]

Excerpts from Bulat Ziganshin's message of Wed Feb 24 14:48:53 -0500 2010:
> > I'd be really curious about techniques that permit mutation during
> > the construction of functional datastructures; this seems like a cool
> > way to get fast performance w/o giving up any of the benefits of
> > immutability.  Unfortunately, my (admittedly short) experiments in
> > this domain ran up against the difficulty that vector didn't let me
> > unsafely freeze its mutable version. :-)
> 
> actually, this technique is already used in haskell. look into array
> library sources, search for freeze

Yup, I'm aware of this.  In fact, vector has thaw/freeze functions for
itself, although it doesn't export them.  I'd rather not have to reimplement
vector just to get this unsafe mutation capability tough (and since the
mutable array GC problem is not fixed for the version of GHC I'm on, I'd likely
see no benefit either).

What I thought was pretty neat about the Clojure approach was how easy they
made it for you to jump into mutation-land and back out again: just a
(transient) call and you're off to the races.  As far as I can tell, you have
to painstakingly write the specific operation you'd like to do via mutation
out using all sorts of unsafe calls.

Cheers,
Edward