[Haskell-cafe] Destructive updates to plain ADTs

Milan Straka fox at ucw.cz
Sun Sep 9 12:03:25 CEST 2012

> > is there any way to perform a destructive update on a plain ADT?
> > Imagine I have a simple
> >   data Tree a = Nil | Node a (Tree a) (Tree a)
> > I would like to be able to modify right subtree of an existing tree.
> >
> > I can do that for example when using IORefs by changing the datatype to
> >   data Tree a = Nil | Node a (IORef (Tree a)) (IORef (Tree a))
> > and use unsafePerformIO + writeIORef. But the IORefs cause additional
> > complexity when working with the data type.
> >
> >
> > At the moment I am interested in any GHC solution, be it non-portable or
> > version specific. I would like just to run some benchmarks and see the
> > results.
> >
> > Cheers,
> > Milan
> You can do it if you refer to the children using Array#s. That's what
> I do in unordered-containers to implement a more efficient fromList.

But the Array# adds another level of indirection, which seem wasteful if
it has 2 elements. Also creating and cloning array is calling method in
runtime, which is another source of (minor) slowdown.

> For arbitrary field types I don't think there's a way (although it
> would be useful when birthing persistent data structures).

That is my reason for asking this.

I was hoping for some Addr# trick or something like that. If
I understand the GHC runtime correctly, rewriting a pointer in an ADT
should not break any garbage collecting and similar.


More information about the Haskell-Cafe mailing list