Как закодировать дерево объектов в Haskell с указателями на родителя и потомка?

Модификация дерева, которая может потребовать частых переходов вверх по пути к корню и обратно, кажется идеальной работой для варианта структуры данных Zipper со «шрамами» в терминологии оригинальной статьи Хьюэта; образцы кода из статьи также предполагают название «запоминание молнии». Конечно, с некоторой осторожностью можно использовать и обычную молнию, но расширенная версия может быть более удобной и/или эффективной в использовании.

Основная идея та же, что и в обычной застежке-молнии, которая уже позволяет перемещаться вверх и вниз по дереву чисто функциональным образом (без каких-либо явных обратных указателей), но операция «вверх», за которой следует операция «вверх». down» становится неоперативной, оставляя фокус на исходном узле (тогда как с обычной застежкой-молнией он переместится на крайний левый брат исходного узла).

Вот ссылка на статью: Жерар Юэ, Функциональная жемчужина: застежка-молния. Это всего лишь шесть страниц, но содержащиеся в них идеи будут очень полезны любому функциональному программисту.

Чтобы ответить на вопрос в вашем заголовке: Да, вы можете создавать узлы, которые имеют ссылки как на своих родителей, так и на своих детей. Пример:

--               parent       children
data Tree = Node (Maybe Tree) [Tree]
root = Node Nothing [a,b] -- I can "forward reference" a and b because haskell is lazy
a = Node (Just root) []
b = Node (Just root) []

Вопрос в том, полезно ли это для вашего конкретного случая использования (часто это не так).

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

Вы на самом деле не описали, какую проблему вы пытаетесь решить, поэтому я не могу сказать вам, как функционально смоделировать то, что вы пытаетесь сделать, но я уверен, что есть способ без изменения дерева.

Вот некоторый код с застежкой-молнией, который демонстрирует простое изменение данных, на которые указывает курсор, а также «глобальное» свойство дерева. Мы строим дерево, перемещаем курсор к узлу, изначально содержащему 1, меняем его на 3, и остаемся с курсором, указывающим на этот узел в полностью обновленном дереве.

import Data.Maybe (fromJust)
import Data.Tree
import Data.Tree.Zipper

type NodeData = Either Bool Int
type TreePath a = [TreePos Full a -> TreePos Full a]

firstChild' = fromJust . firstChild
parent'     = fromJust . parent
prev'       = fromJust . prev
next'       = fromJust . next

-- Determine the path from the root of the tree to the cursor.
pathToMe :: TreePos Full NodeData -> TreePath NodeData
pathToMe t | isRoot t  = []
           | isFirst t = firstChild' : pathToMe (parent' t)
           | otherwise = next' : pathToMe (prev' t)

-- Mark a tree as invalid, but leave the cursor in the same place.
invalidate :: TreePos Full NodeData -> TreePos Full NodeData
invalidate t = foldr ($) (setLabel (Left False) (root t)) (pathToMe t)

-- Set a node's internal data.
setData :: Int -> TreePos Full NodeData -> TreePos Full NodeData
setData = (invalidate . ) . setLabel . Right

main = let tree1 = Node (Left True) [Node (Right 1) [], Node (Right 2) []]
           Just cursor = firstChild (fromTree tree1)
           tree2 = setData 3 cursor
       in do putStrLn (drawTree (fmap show tree1))
             putStrLn (drawTree (fmap show (toTree tree2)))
             putStrLn $ "Cursor at "++show (label tree2)

Выход:

Left True
|
+- Right 1
|
`- Right 2

Left False
|
+- Right 3
|
`- Right 2

Cursor at Right 3

У меня не так много опыта работы с Haskell, но, насколько мне известно, в чисто функциональных языках невозможно иметь круги в эталонном графе. Это означает, что:

1. У вас не может быть двусторонних списков, детей в деревьях, указывающих на своих родителей и т. д.*
2. Обычно недостаточно изменить только один узел. Любой измененный узел требует изменений в каждом узле, начиная с «корня» структур данных и заканчивая узлом, который вы хотите изменить.

Суть в том, что я бы не стал брать алгоритм Java (или любого другого императивного языка) и пытаться преобразовать его в Haskell. Вместо этого попробуйте найти более функциональный алгоритм (и, возможно, даже другую структуру данных) для решения проблемы.

ИЗМЕНИТЬ:

Из вашего разъяснения не совсем ясно, нужно ли вам аннулировать только прямого родителя объекта, который изменился, или всех его предков в иерархии, но на самом деле это не имеет большого значения. Поскольку аннулирование объекта в основном означает его изменение, а это невозможно, вам в основном нужно создать измененный дубликат этого объекта, а затем вы должны сделать так, чтобы его родительский объект указывал на него, поэтому вам также нужно создать новый объект для этого . Это продолжается до тех пор, пока вы не доберетесь до корня. Если у вас есть некоторая рекурсия для обхода дерева, чтобы «модифицировать» ваш объект, вы можете воссоздать путь от этого объекта к корню на выходе из рекурсии.

Надеюсь, это имело смысл. :с

* Как указано в комментариях jberryman и в других ответах, в Haskell можно создавать круговые ссылочные графы, используя ленивую оценку.

Изучите использование экземпляра Functor типа Maybe.

Например, ваша проблема может быть примерно такой: вы хотите вставить элемент в двоичное дерево, но только если его еще нет. Вы можете сделать это с помощью чего-то вроде:

data Tree a = Node a (Tree a) (Tree a)
            | Tip

maybeInsert :: a -> Tree a -> Maybe (Tree a)
maybeInsert a Tip = Just $ Node a Tip Tip
maybeInsert a (Node a' l r)
    | a == a' = Nothing
    | a < a'  = fmap (\l'-> Node a' l' r) (maybeInsert a l)
    | a > a'  = fmap (\r'-> Node a' l r') (maybeInsert a r)

Таким образом, функция вернет Nothing, если мы обнаружили, что элемент уже присутствует, или вернет Just новое дерево со вставленным элементом.

Надеюсь, это имеет отношение к тому, что вы пытаетесь сделать.

Разве лень не может позаботиться о том, чтобы проверка не происходила слишком часто? Таким образом, вам не нужно хранить поле m_valid.

Например, если вы проверяете только при сохранении, то вы можете редактировать объекты по своему вкусу, без повторной проверки все время; только когда пользователь нажимает кнопку «Сохранить», вычисляется значение validateDoc. Поскольку я не знаю наверняка, что означает ваше понятие валидности и для чего оно вам нужно, я могу быть совершенно прав.

Непроверенный и неполный код:

data Document = Document { subDocs :: [SubDoc] }
data SubDoc = SubDoc { content :: String }

addSubDoc :: SubDoc -> (Document -> Document)
addSubDoc = error "not yet implemented: addSubDoc"

modifySubDoc :: Int -> (SubDoc -> SubDoc) -> (Document -> Document)
modifySubDoc = error "not yet implemented: modifySubDoc"


validateDoc :: Document -> Bool
validateDoc = all validateSubDoc . subDocs

validateSubDoc :: SubDoc -> Bool
validateSubDoc = not . null . contents

Я предполагаю, что общая достоверность документа зависит только от вложенных документов (здесь они моделируются путем проверки того, что они содержат непустую строку).

Кстати, я думаю, вы забыли a.addChild(b); в main.