什么haskell数据结构来存储可变的树
我想在haskell编写浏览器。*数据结构将是代表文档的可变树。除了使用完全由iorefs组成的树,还有更好的解决方案吗?什么haskell数据结构来存储可变的树
我希望能避免这样的事情:data DomNode = DomNode TagName NodeProperties (IORef DomNode) [IORef DomNode]
(标签,属性,父母,子女)
的问题是,JavaScript可以守住节点引用的树,它可以发生变异(添加子,修改属性)它引用的任何节点,以及遍历它的父节点。
编辑:
我意识到你将需要以某种方式使用可变的状态 - 因为你可以稳守于从树中删除,或者在树上移动的节点的引用。如果你通过基于树结构的东西来引用元素,那么这个引用将是无效的。
对于JavaScript来说,使用可变引用是很自然的,所以你必须迟早介绍它们(不一定是IORef
s,也许某种查询表生活在monad状态)。
如果DOM上的大部分操作都是从javascript执行的,那么最好选择自然的数据结构。
不要尝试仅将纯数据结构用于纯度本身。否则,你会完成手工制作RAM的模拟:)你的任务看起来势在必行,那么为什么不使用haskell提供的所有命令功能呢?
我不认为拉链,正如Niklas B.所建议的,可以帮助你很多。通常他们只有一个“光标”,在那里你可以进行变异。 (AFAIK理论上任何数量的游标都是可能的,但实际上它大多是不可用的)
实际上,Store comonad可以非常优雅地处理多个索引。您只需要将游标类型添加到每个索引 – 2013-02-12 11:58:21
@GabrielGonzalez的产品中就知道了。你能指点我一些相关的阅读吗? (最好是像我这样的类别理论假人:)) – Yuras 2013-02-12 12:08:20
还没有。尽管如此,我正在撰写一篇关于comonads的博客文章,这就是为什么这个话题在我的脑海里变得新鲜。 – 2013-02-12 12:22:56
通常的Haskell方法是使用不可变树,并且有诸如addChild
之类的操作返回一个新的,修改过的树,而不是触摸现有的树。
不知道你真的想要做与这棵树,我会建议这可能是最简单和最简单的方法。
也许使用[拉链](http://www.haskell.org/haskellwiki/Zipper)? – 2013-02-12 01:49:40