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

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

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

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

РЕДАКТИРОВАТЬ:

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

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

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

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

--               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) []

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

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

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

Разве лень не позаботится о том, чтобы проверка не происходила слишком часто? Таким образом, вам не нужно сохранять поле 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 .

Вот код на молнии, который демонстрирует легкое изменение данных, на которые указывает курсор, а также "глобального" свойства дерева. Мы строим дерево, перемещаем курсор в узел, изначально содержащий 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

Рассмотрите возможность использования 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 новое дерево с вставленным элементом.

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

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

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

Вот ссылка на статью: Gérard Huet, Functional Pearl: The Zipper. В ней всего шесть страниц, но идеи, содержащиеся в ней, очень полезны для любого функционального программиста.