Соберите данные о существующих древовидных данных

Question

Предположим, что у нас есть древовидные данные, и мы хотели бы добавить информацию о глубине каждого узла. Как мы можем легко достичь этого?

Data Tree = Node Tree Tree | Leaf 

Для каждого узла мы хотели бы знать в постоянной сложности, насколько он глубокий. У нас есть данные из внешнего модуля, поэтому у нас есть информация, как показано выше. Реальный пример - это внешний HTML-парсер, который просто предоставляет дерево XML, и мы хотели бы собрать данные, например. сколько гиперссылок содержит каждый узел.

Функциональные языки созданы для перемещения деревьев и сбора данных, должно быть простое решение.

Очевидное решение будет создавать параллельную структуру. Мы можем сделать лучше?

Answer 1

Стандартный трюк, который я узнал из замечательного замечательного Криса Окасаки Purely Functional Data Structures, - это кеширование результатов дорогостоящих операций на каждом узле. (Возможно, этот трюк был известен до тезиса Окасаки, я не знаю.) Вы можете предоставить умных конструкторов для управления этой информацией для вас, чтобы построить дерево не нужно было больно. Например, когда дорогостоящая операция глубины, вы можете написать:

module SizedTree (SizedTree, sizedTree, node, leaf, depth) where 

data SizedTree = Node !Int SizedTree SizedTree | Leaf 

node l r = Node (max (depth l) (depth r) + 1) l r 
leaf = Leaf 

depth (Node d _ _) = d 
depth Leaf = 0 

-- since we don't expose the constructors, we should 
-- provide a replacement for pattern matching 
sizedTree f v (Node _ l r) = f l r 
sizedTree f v Leaf = v 

Построение SizedTree сек стоит O (1) дополнительную работу на каждом узле (следовательно, O (п) работать, чтобы преобразовать н-узел Tree до SizedTree), но выигрыш в том, что проверка глубины SizedTree - или любого поддерева - является операцией O (1).

Answer 2

Вам нужны другие данные, где вы можете хранить эти Int s. Определение Tree в

data Tree a = Node Tree a Tree | Leaf a 

, а затем написать функцию

annDepth :: Tree a -> Tree (Int, a) 

Оригиналы Tree является Tree() и с узором синонимов можно восстановить хорошие конструкторы.

---

Если вы хотите сохранить оригинальное дерево по какой-то причине, вы можете определить вид:

{-# LANGUAGE GADTs, DataKinds #-} 

data Shape = SNode Shape Shape | SLeaf 

data Tree a sh where 
    Leaf :: a -> Tree a SLeaf 
    Node :: Tree a lsh -> a -> Tree a rsh -> Tree a (SNode lsh rsh) 

При этом у вас есть гарантия, что аннотированный дерево имеет ту же форму, что и Неаннотированный. Но это не работает хорошо без соответствующих зависимых типов.

---

Кроме того, обратите внимание на вопросе Boilerplate-free annotation of ASTs in Haskell?

Answer 3

Стандартное решение является то, что предложил @DanielWagner, просто расширить структуру данных. Это может быть несколько неудобно, но может быть решено: интеллектуальные конструкторы для создания экземпляров и использования records for pattern matching.

Возможно, Data types a la carte может помочь, хотя я сам не использовал этот подход. На основании этого есть библиотека compdata.

Совершенно другой подход заключается в том, чтобы эффективно запоминать нужные вам значения.Я пытался решить similar problem, и одно из решений предоставлено библиотекой stable-memo. Обратите внимание, что это не чисто функциональный подход, поскольку библиотека внутренне основана на идентичности объекта, но интерфейс чист и отлично работает для этой цели.