在 Mathematica 中,您所做的大部分工作都是基于表达式。表达式自然具有树结构。对于深度优先遍历(这可能是最常见的),您可以使用类似的函数Scan
,Map
, Cases
与更传统的语言的区别在于,没有简单的方法来保存表达式树中单个节点的身份,因为 Mathematica 中没有指针。此外,当您只需要在几个地方修改表达式时,Mathematica 中惯用的许多表达式操作都会复制整个表达式,因为表达式是不可变的。
使用不可变的 Mathematica 表达式作为树仍然有几个优点。一是,因为它们是不可变的,所以只需查看它们就很容易理解它们存储的内容(状态和行为不混合)。另一个是有高效且通用的函数,例如Map
, MapIndexed
or Scan
,遍历它们。例如,访客设计模式是无形的 http://norvig.com/design-patterns/- 这只是Map[f,tree,Infinity]
,内置于语言中。此外,还有一些内置功能,例如Cases
, Replace
, ReplaceAll
等等,它允许人们编写非常简洁和声明性的代码来解构树,找到具有特定语法或满足某些条件的树的片段等。由于树不限于仅从列表构建并且从不同的头构建,所以一可以有效地使用它来编写非常简洁的树处理代码。最后,本着探索性和自下而上的编程 http://www.paulgraham.com/progbot.html,这缩短了开发周期并最终带来更好的设计。
也就是说,您当然可以实现“有状态”(可变)树数据结构。我怀疑,尚未完成的真正原因通常是与构建、修改和遍历这样一棵树相关的性能影响,因为它的每一步都会经历完整的符号评估过程(请参阅this https://stackoverflow.com/questions/4721171/performance-tuning-in-mathematica/4723969发布有关更多详细信息)。有关如何在 Mathematica 上下文中使用二叉搜索树以获得非常高效的代码的 2 个示例,请参阅我的帖子here https://stackoverflow.com/questions/5018252/a-variation-of-integerpartition/5019949#5019949(通用符号设置)和here https://stackoverflow.com/questions/5246330/delete-repeating-list-elements-preserving-order-of-appearance/5251034#5251034(在编译代码的上下文中)。对于在 Mathematica 中惯用地构造数据结构的一般方法,我推荐 Roman Maeder 的书籍:“Mathematica 中的编程”、“Mathematica 程序员 I&II”,尤其是“Mathematica 中的计算机科学”。在后者中,他详细讨论了如何在 Mathematica 中实现二叉搜索树。EDIT正如 @Simon 提到的,@Daniel Lichtblau 的演讲也是一个很好的资源,它展示了如何构建数据结构并使其高效。
关于在 Mathematica 中实现包含某些状态的数据结构的一般方法,这里是从我的帖子中摘录的一个简单示例this http://groups.google.com/group/comp.soft-sys.math.mathematica/browse_thread/thread/ec4958c35f99758d/Mathgroup 线程 - 它实现“对”数据结构。
Unprotect[pair, setFirst, getFirst, setSecond, getSecond, new, delete];
ClearAll[pair, setFirst, getFirst, setSecond, getSecond, new, delete];
Module[{first, second},
first[_] := {};
second[_] := {};
pair /: new[pair[]] := pair[Unique[]];
pair /: pair[tag_].delete[] := (first[tag] =.; second[tag] =.);
pair /: pair[tag_].setFirst[value_] := first[tag] = value;
pair /: pair[tag_].getFirst[] := first[tag];
pair /: pair[tag_].setSecond[value_] := second[tag] = value;
pair /: pair[tag_].getSecond[] := second[tag];
Format[pair[x_Symbol]] := "pair[" <> ToString[Hash[x]] <> "]";
];
Protect[pair, setFirst, getFirst, setSecond, getSecond, new, delete];
以下是您可以如何使用它:
pr = new[pair[]];
pr.setFirst[10];
pr.setSecond[20];
{pr.getFirst[], pr.getSecond[]}
{10, 20}
创建新的pair对象列表:
pairs = Table[new[pair[]], {10}]
{"pair[430427975]", "pair[430428059]", "pair[430428060]", "pair[430428057]",
"pair[430428058]", "pair[430428063]", "pair[430428064]", "pair[430428061]",
"pair[430428062]", "pair[430428051]"}
设置字段:
Module[{i},
For[i = 1, i <= 10, i++,
pairs[[i]].setFirst[10*i];
pairs[[i]].setSecond[20*i];]]
检查字段:
#.getFirst[] & /@ pairs
{10, 20, 30, 40, 50, 60, 70, 80, 90, 100}
#.getSecond[] & /@ pairs
{20, 40, 60, 80, 100, 120, 140, 160, 180, 200}
在我提到的帖子中有更详细的讨论。以这种方式创建的“对象”的一个大问题是它们没有自动垃圾收集,这可能是顶级 Mathematica 本身实现的 OOP 扩展没有真正起飞的主要原因之一。
Mathematica 有几个 OOP 扩展,例如classes.m
Roman Maeder 的软件包(来源在他的“Mathematica Programmer”书中),Objectica
商业包和其他几个。但是,在 Mathematica 本身提供有效的机制(可能基于某种指针或引用机制)来构建可变数据结构(如果发生这种情况)之前,与此类数据结构的顶级实现相关的性能可能会受到很大影响在MMA。此外,由于 mma 基于不变性作为核心思想之一,因此使可变数据结构与 Mathematica 编程的其他习惯很好地契合并不容易。
EDIT
这是一个与上面示例类似的简单状态树实现:
Module[{parent, children, value},
children[_] := {};
value[_] := Null;
node /: new[node[]] := node[Unique[]];
node /: node[tag_].getChildren[] := children[tag];
node /: node[tag_].addChild[child_node, index_] :=
children[tag] = Insert[children[tag], child, index];
node /: node[tag_].removeChild[index_] :=
children[tag] = Delete[children[tag], index];
node /: node[tag_].getChild[index_] := children[tag][[index]];
node /: node[tag_].getValue[] := value[tag];
node /: node[tag_].setValue[val_] := value[tag] = val;
];
一些使用示例:
In[68]:= root = new[node[]]
Out[68]= node[$7]
In[69]:= root.addChild[new[node[]], 1]
Out[69]= {node[$8]}
In[70]:= root.addChild[new[node[]], 2]
Out[70]= {node[$8], node[$9]}
In[71]:= root.getChild[1].addChild[new[node[]], 1]
Out[71]= {node[$10]}
In[72]:= root.getChild[1].getChild[1].setValue[10]
Out[72]= 10
In[73]:= root.getChild[1].getChild[1].getValue[]
Out[73]= 10
有关使用此可变树数据结构的一个重要示例,请参阅this https://stackoverflow.com/questions/6138540/code-manipulation-via-interactive-tree-for-mathematica/6140400#6140400我的帖子。它还将这种方法与更加重用 Mathematica 本地数据结构和函数的方法进行对比,并很好地说明了本文开头讨论的要点。