What haskell data structure to store mutable tree

Question

I was thinking about writing a browser in haskell. A central data structure will be a mutable tree representing the document. Apart from using a tree composing entirely of iorefs, is there a better solution?

I am hoping to avoid something like this: data DomNode = DomNode TagName NodeProperties (IORef DomNode) [IORef DomNode] (tag, properties, parent, children)

The problem is that javascript can hold onto references of nodes in the tree, and it can mutate (add children, modify properties) any node it has a reference to, as well as traverse to it's parent.

Edit:

I realized you would need to use mutable state somehow - because you can hold onto a reference to a node that is deleted from the tree, or moved in the tree. If you referred to the element via something based on the structure of the tree, this reference will be invalid.

Answer 1

It is natural for javascript to operate with mutable references, so you'll have to introduce them sooner or later (not necessarily IORefs, maybe some kind of lookup table living in state monad).

If most of operations on DOM will be performed from javascript, then it is better to select data structure natural for it.

Don't try to use pure data structure only for purity itself. Otherwise you'll finish with hand-made emulation of RAM :) Your task looks imperative for me, so why not to use all the imperative features haskell provides?

I don't think zippers, as Niklas B. suggested, can help you a lot. Usually they have only one "cursor", where you can mutate. (AFAIK in theory any number of cursors are possible, but in practice it is mostly unusable)

Answer 2

The usual Haskell approach is to use an immutable tree, and have operations such as addChild and so forth return a new, modified tree, rather than touching the existing tree.

Without knowing what you're actually trying to do with this tree, I would suggest that this is probably the simplest and easiest approach.