В Mathematica большая часть того, что вы делаете, основана на выражениях. Выражения естественно имеют древовидную структуру. Для обходов в глубину (которые, вероятно, наиболее распространены) вы можете использовать такие функции, как Scan, Map, Cases и т. Д. Разница по сравнению с более традиционными языками заключается в том, что не существует простого способа сохранить идентичность отдельного узла в дереве выражений, так как в Mathematica нет указателей. Кроме того, многие операции с выражениями, которые являются идиоматическими в Mathematica, копируют все выражение, когда вам нужно только изменить его в нескольких местах, потому что выражения неизменны.
Использование неизменяемых выражений Mathematica в качестве деревьев по-прежнему имеет ряд преимуществ. Во-первых, поскольку они неизменны, легко понять, что они хранят, просто взглянув на них (состояние и поведение не смешаны). Другое состоит в том, что существуют эффективные и общие функции, такие как Map, MapIndexed или Scan, которые пересекают их. Например, шаблон дизайна посетителя невидим - это просто Map[f,tree,Infinity], встроенный в язык. Кроме того, есть встроенные функции, такие как Cases, Replace, ReplaceAll и т. Д., Которые позволяют писать очень лаконичный и декларативный код для деструктурирования деревьев, поиска фрагментов деревьев с определенным синтаксисом или выполнения некоторого условия, и т. д. Поскольку деревья не ограничиваются только построением из списков и построением из разных глав, можно эффективно использовать это для написания очень краткого кода обработки дерева. Наконец, свобода очень легко создавать любую желаемую древовидную структуру значительно упрощает проведение экспериментов и создание прототипов в духе исследовательского и восходящего программирования , которое сокращает цикл разработки и в конечном итоге приводит к лучший дизайн.
Тем не менее, вы, безусловно, можете реализовать структуру данных "изменяемого состояния" (изменяемого) дерева. Реальная причина, по которой это еще не было сделано, - это, как я подозреваю, снижение производительности, связанное со сборкой, изменением и обходом такого дерева, поскольку оно будет проходить полный процесс символьной оценки на каждом этапе (см. this пост для более подробной информации об этом). 2 примера того, как, например, двоичное дерево поиска можно использовать в контексте Mathematica для довольно эффективного кода, см. В моих сообщениях здесь (общая символьная настройка) и здесь (в контекст скомпилированного кода). Для общих способов построения структур данных идиоматически в Mathematica, я рекомендую книги Романа Медера: «Программирование в Mathematica», «Mathematica programmer I & II» и особенно «Информатика в Mathematica». В последнем у него есть подробное обсуждение того, как реализовать двоичное дерево поиска в Mathematica. EDIT Как упоминал @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}
Создание списка новых парных объектов:
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 верхнего уровня, действительно не взлетели.
Существует несколько расширений ООП для Mathematica, например, пакет classes.m Романа Мейдера (источник находится в его книге "Программист Mathematica"), коммерческий пакет Objectica и некоторые другие. Но до тех пор, пока сама Mathematica не предоставит эффективные механизмы (возможно, основанные на каком-либо механизме указателей или ссылок) для построения изменяемых структур данных (если это когда-либо произойдет), вероятно, будет существенное снижение производительности, связанное с реализациями таких структур данных верхнего уровня. в мма. Кроме того, поскольку 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 и хорошо иллюстрирует моменты, обсуждавшиеся в начале этого поста.