В Clojure, когда деревья гетерогенных типов узлов должны быть представлены с использованием записей или векторов?

Question

Что является лучшей практикой идиоматического замыкания для представления дерева, состоящего из различных типов узлов:

A.построение деревьев из нескольких различных типов записей, которые определяются с использованием deftype или defrecord:

(defrecord node_a [left right])
(defrecord node_b [left right])
(defrecord leaf [])

(def my-tree (node_a. (node_b. (leaf.) (leaf.)) (leaf.)))

B.построение деревьев из векторов с ключевыми словами, обозначающими типы:

(def my-tree [:node-a [:node-b :leaf :leaf] :leaf])

Большинство кодов, которые я вижу, похоже, предпочитают использовать структуры данных общего назначения (векторы, карты и т. д.), а не типы данныхили записи.Иккинг, если взять один пример, очень хорошо представляет html с использованием подхода vector + keyword.

Когда нам следует отдавать предпочтение одному стилю перед другим?

Answer 1

Это хороший вопрос.Я думаю, что оба подходят для разных видов проблем.Вложенные векторы являются хорошим решением, если каждый узел может содержать переменный набор информации - в частности, системы шаблонов будут работать хорошо.Записи являются хорошим решением для небольшого числа фиксированных типов узлов, где вложение гораздо более ограничено.

Мы много работаем с разнородными деревьями записей.Каждый узел представляет один из нескольких известных типов, каждый из которых имеет свой набор известных фиксированных ключей.Причиной того, что записи лучше в этом случае, является то, что вы можете выбрать данные из узла по ключу, который является O (1) (на самом деле вызов метода Java очень быстрый), а не O (n) (где вы должны искатьчерез содержимое узла), а также, как правило, более легкий доступ.

Записи в 1.2 не совсем "закончены", но создать их самому довольно просто.У нас есть defrecord2 , который добавляет функции конструктора (new-foo), проверку полей, поддержку печати, поддержку pprint, поддержку обхода / редактирования дерева через молнии и т. Д.

Пример того, где мыиспользуйте это для представления AST или планов выполнения, где узлами могут быть такие вещи, как Join, Sort и т. д.

Векторы будут лучше для создания таких вещей, как строки, где в каждый узел может быть помещено произвольное количество вещей,Если вы можете поместить 1+

s в

, то вы не можете создать запись, которая содержит поле: p - это просто не имеет никакого смысла.Это тот случай, когда векторы гораздо более гибкие и идиоматические.

Answer 2

Вы можете поместить в вектор столько элементов, сколько захотите. Запись имеет заданное количество полей. Если вы хотите ограничить свои узлы только N подузлами, записи могут быть хорошими, например, создание когда бинарное дерево, где узел должен иметь только левый и правый. Но для чего-то вроде HTML или XML вы, вероятно, захотите поддерживать произвольное количество подузлов.

Использование векторов и ключевых слов означает, что «расширить» набор поддерживаемых типов узлов так же просто, как вставить новое ключевое слово в вектор. [:frob "foo"] нормально работает в Hiccup, даже если его автор никогда не слышал о лягушках. Используя записи, вам, возможно, придется определить новую запись для каждого типа узла. Но тогда вы получаете возможность ловить опечатки и проверять подузлы. [:strnog "some bold text?"] не будет пойман Hiccup, но (Strnog. "foo") будет ошибкой во время компиляции.

Векторы, являющиеся одним из основных типов данных Clojure, вы можете использовать встроенные функции Clojure для управления ими. Хотите расширить свое дерево? Просто conj на него, или update-in, или что угодно. Вы можете построить свое дерево постепенно таким образом. С записями вы, вероятно, застряли в вызовах конструктора, иначе вам придется написать тонну функций-оболочек для конструкторов.

Похоже, что это частично сводится к аргументу динамического против статического. Лично я бы пошел по динамическому маршруту (вектор + ключевое слово), если не было особой необходимости в преимуществах использования записей. Вероятно, проще кодировать таким образом, и он более гибок для пользователя, за счет того, что пользователю легче в итоге создавать беспорядок. Но пользователи Clojure, вероятно, привыкли обращаться с опасным оружием на регулярной основе. Clojure - это во многом динамический язык, поэтому часто нужно оставаться динамичным.