我主要将Mathematica用作数学工作台和编写相对较小的临时程序。但是，我正在设计一个系统，并打算用Mathematica进行编程。我需要在树中存储数据，并搜索和遍历该树。虽然我知道如何实现树，但我更喜欢标准、经过测试的代码。我查看了Mathematica用户维基上提供的基本数据结构包的类型。我没有找到任何包，尽管Mathematica文档中有一个小例子。
现在是我的问题：
是否有（开源的）数据结构包可供使用？
你采取了什么方法来处理数据结构？逐步开发自己的实用程序包吗？
（不是问题，只是一句话备注。也许……缺乏（大量可用的）开源软件包就是Mathematica没有得到应有动力的原因。这是个鸡生蛋的问题，我很担心。）
在Mathematica中，大部分工作都基于表达式。表达式自然具有树形结构。对于深度优先遍历（可能是最常见的），您可以使用像Scan、Map、Cases等函数。与更传统的语言相比，差异在于，在表达式树中保留单个节点的标识没有简单的方法，因为在Mathematica中没有指针。此外，许多在Mathematica中惯用的表达式操作会复制整个表达式，而您只需要在几个地方修改它，因为表达式是不可变的。
将不可变的Mathematica表达式用作树仍然具有几个优点。其中一个优点是，因为它们是不可变的，通过查看它们就很容易理解它们存储了什么（状态和行为没有混合）。另一个优点是，有一些高效且通用的函数，例如Map、MapIndexed或Scan，可以遍历它们。例如，访问者设计模式是隐式的 - 它只是内置语言的Map[f,tree,Infinity]。此外，还有内置函数，例如Cases、Replace、ReplaceAll等，允许编写非常简洁和声明性的代码来解构树、找到具有某些语法或满足某些条件的树的部分等。由于树不仅限于仅从列表构建并且可以从不同的头部构建，因此可以有效地使用它来编写非常简洁的树处理代码。最后，非常容易自由构建任何想要的树结构，这使得执行实验和原型设计变得更加容易，符合探索性和自底向上编程的精神，缩短了开发周期，并最终导致更好的设计。
尽管如此，你当然可以实现“有状态”的（可变的）树形数据结构。一般而言，这样做之所以还没有被实现，我认为原因是与构建、修改和遍历此类树形结构相关的性能损失，因为它将在每个步骤中经历完整的符号评估过程（请参见此帖子了解更多详细信息）。例如，二叉搜索树如何在Mathematica环境中用于编写相当高效的代码，请参见我的帖子这里（通用符号设置）和这里（在编译代码的上下文中）。有关在Mathematica中惯用地构造数据结构的一般方法，我推荐Roman Maeder的书籍："Programming in Mathematica"，"Mathematica programmer I&II"，特别是"Computer Science in Mathematica"。在后者中，他详细讨论了如何在Mathematica中实现二叉搜索树。编辑正如@Simon所提到的，@Daniel Lichtblau的演讲也是一个很好的资源，它展示了如何构建数据结构并使它们高效。
关于在Mathematica中实现具有一定状态的数据结构的一般方法，以下是一个简单的例子，提取自我在这个 Mathgroup线程中发布的帖子- 它实现了一个“pair”数据结构。
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扩展，例如Roman Maeder的classes.m包（源代码在他的“Mathematica Programmer”书中），商业软件Objectica和其他几个。但是，在Mathematica本身提供有效机制之前（也许基于某种指针或引用机制）来构建可变数据结构（如果这发生了），在mma中实现此类数据结构的顶层实现可能会有很大的性能损失。此外，由于mma以不变性作为核心思想之一，因此很难使可变数据结构与Mathematica编程的其他习惯语言很好地融合。
编辑
以下是类似于上面示例的精简状态树实现：
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
一个使用这种可变树数据结构的非平凡示例，请参见我的这篇文章。它还将这种方法与更重度重用Mathematica本地数据结构和函数的方法进行了对比，并很好地说明了本文开头讨论的要点。
safe[{x0_, y0_}][{x1_, y1_}] :=
x0 != x1 && y0 != y1 && x0 - y0 != x1 - y1 && x0 + y0 != x1 + y1
filter[_, {}] := {}
filter[p_, {h_, t_}] := If[p[h], {h, filter[p, t]}, filter[p, t]]
search[n_, nqs_, qs_, {}, a_] := If[nqs == n, a + 1, a]
search[n_, nqs_, qs_, {q_, ps_}, a_] :=
search[n, nqs, qs, ps,
search[n, nqs + 1, {q, qs}, filter[safe[q], ps], a]]
ps[n_] :=
Fold[{#2, #1} &, {}, Flatten[Table[{i, j}, {i, n}, {j, n}], 1]]
solve[n_] := search[n, 0, {}, ps[n], 0]
这里是等效的 F# 代码：
let safe (x0, y0) (x1, y1) =
x0<>x1 && y0<>y1 && x0-y0<>x1-y1 && x0+y0<>x1+y1
let rec filter f = function
| [] -> []
| x::xs -> if f x then x::filter f xs else filter f xs
let rec search n nqs qs ps a =
match ps with
| [] -> if nqs=n then a+1 else a
| q::ps ->
search n (nqs+1) (q::qs) (filter (safe q) ps) a
|> search n nqs qs ps
let ps n =
[ for i in 1..n do
for j in 1..n do
yield i, j ]
let solve n = search n 0 [] (ps n) 0
solve 8
let rand = System.Random()
let xs = List.init 10000 (fun _ -> rand.Next 100)
Array.init 100 (fun _ ->
let t = System.Diagnostics.Stopwatch.StartNew()
ignore(List.length xs)
t.Elapsed.TotalSeconds)
Dispatch。