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.

Maybe use a zipper?

Niklas B.
– Niklas B.

2013-02-12 01:49:40 +00:00
Commented Feb 12, 2013 at 1:49 — Niklas B.
– Niklas B., Commented Feb 12, 2013 at 1:49

Yuras · Accepted Answer · 2013-02-12 02:30:11Z

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)

answered Feb 12, 2013 at 2:30

Yuras

13.9k1 gold badge49 silver badges61 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Gabriella Gonzalez Over a year ago

Actually, the Store comonad handles multiple indices quite elegantly. You just the cursor type to the product of each index

Yuras Over a year ago

@GabrielGonzalez good to know. could you please point me to any related reading? (preferably for category-theoretic dummies like me :) )

Gabriella Gonzalez Over a year ago

Not yet. I am writing up a blog post on comonads for just such a purpose, though, which is why the topic is fresh on my mind.

MathematicalOrchid · Accepted Answer · 2013-02-12 08:56:25Z

1

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.

answered Feb 12, 2013 at 8:56

MathematicalOrchid

63.1k21 gold badges131 silver badges231 bronze badges

Collectives™ on Stack Overflow

What haskell data structure to store mutable tree

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related