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

Question

У меня следующая проблема: у меня есть дерево объектов разных классов, где действие в дочернем классе делает родитель недействительным. В императивных языках это тривиально. Например, в Java:

public class A {
    private List<B> m_children = new LinkedList<B>();
    private boolean m_valid = true;

    public void invalidate() {
        m_valid = false;
    }

    public void addChild(B child) {
        m_children.add(child);
        child.m_parent = this;
    }
}

public class B {
    public A m_parent = null;
    private int m_data = 0;

    public void setData(int data) {
        m_data = 0;
        m_parent.invalidate();
    }
}

public class Main {
    public static void main(String[] args) {
        A a = new A();
        B b = new B();
        b.setData(0); //invalidates A
    }
}

Как мне сделать вышеперечисленное в Haskell? Я не могу сосредоточиться на этом, так как после того, как я создаю объект в Haskell, его нельзя изменить.

Я был бы очень признателен, если бы опубликован соответствующий код на Haskell.

РЕДАКТИРОВАТЬ: проблема, которую я пытаюсь решить, следующая:

У меня есть приложение, которое редактирует документы. Документ - это иерархия объектов. Когда свойства дочерних объектов изменены, документ должен быть установлен в недопустимое состояние, чтобы пользователь знал, что документ должен быть проверен.

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

EDIT:

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

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

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

Answer 5

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

Answer 6

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

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