8

次の問題があります。子クラスのアクションが親を無効にする、さまざまなクラスのオブジェクトのツリーがあります。命令型言語では、行うのは簡単です。たとえば、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コードが投稿されている場合、私は非常に義務付けられています.

編集:私が解決しようとしている問題は次のとおりです。

ドキュメントを編集するアプリケーションがあります。ドキュメントは、オブジェクトの階層です。子オブジェクトのプロパティが変更された場合、ユーザーがドキュメントを検証する必要があることを認識できるように、ドキュメントを無効な状態に設定する必要があります。

4

6 に答える 6

7

Huet による元の論文の用語では、ルートまでのパスを頻繁に移動して戻る必要があるツリーを変更することは、「傷跡」のある Zipper データ構造のバリアントにとって完璧な仕事のように思えます。論文のコードサンプルは、「記憶ジッパー」の名前も示唆しています。もちろん、注意して通常のジッパーを使用することもできますが、拡張バージョンの方が便利で効率的です。

基本的な考え方は、通常のジッパーの背後にあるものと同じです。これにより、純粋に機能的な方法で (明示的なバックポインターなしで) ツリーを上下に移動できますが、「go up」操作の後に「go」操作が続きます。 down" 操作はノーオペレーションになり、元のノードにフォーカスを残します (通常のジッパーでは元のノードの左端の兄弟に移動します)。

論文へのリンクは次のとおりです: Gérard Huet, Functional Pearl: The Zipper . わずか 6 ページですが、そこに含まれるアイデアは関数型プログラマーにとって非常に役立ちます。

于 2010-06-07T16:01:15.990 に答える
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) []

問題は、それが特定のユースケースに役立つかどうかです (多くの場合、そうではありません)。

今、あなたの体の質問: あなたは正しいです、作成された後に値を変更することはできません。したがって、有効なツリーを取得すると、そのツリーを参照する変数がスコープ内にある限り、常に有効なツリーが保持されます。

あなたが解決しようとしている問題を実際に説明していないので、あなたがしようとしていることを機能的にモデル化する方法を教えることはできませんが、ツリーを変更せずに方法があると確信しています.

于 2010-06-07T15:28:05.333 に答える
3

以下は、カーソルが指すデータとツリーの「グローバル」プロパティの簡単な変更を示すジッパー コードです。ツリーを作成し、最初に 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
于 2010-06-07T16:52:36.813 に答える
2

Haskell の経験はあまりありませんが、私が知る限り、純粋な関数型言語では参照グラフに円を含めることはできません。つまり、次のことを意味します。

  1. 双方向リスト、親を指しているツリー内の子などを持つことはできません*
  2. 通常、1 つのノードだけを変更するだけでは十分ではありません。変更されたノードはすべて、データ構造の「ルート」から変更したいノードまでのすべてのノードで変更が必要です。

肝心なのは、Java (またはその他の命令型言語) アルゴリズムを取得して Haskell に変換しようとはしないということです。代わりに、問題を解決するために、より機能的なアルゴリズム (および場合によっては別のデータ構造) を見つけてみてください。

編集：

あなたの明確化から、変更されたオブジェクトの直接の親のみを無効にする必要があるかどうか、または階層内のすべての祖先を無効にする必要があるかどうかは完全には明らかではありませんが、実際にはそれほど重要ではありません。オブジェクトを無効にすることは基本的にそれを変更することを意味し、それは不可能であるため、基本的にそのオブジェクトの変更された複製を作成する必要があり、次にその親がそれを指すようにする必要があるため、そのための新しいオブジェクトも作成する必要があります. これは、根に到達するまで続きます。オブジェクトを「変更」するためにツリーをたどる再帰がある場合は、再帰から抜け出す途中で、そのオブジェクトからルートへのパスを再作成できます。

それが理にかなっていることを願っています。:s

* jberryman のコメントや他の回答で指摘されているように、遅延評価を使用して Haskell で循環参照グラフを作成することは可能です。

于 2010-06-07T15:23:33.080 に答える
0

怠惰は、検証があまり頻繁に行われないようにすることはできませんでしたか? 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。

于 2010-06-08T10:56:33.280 に答える
0

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、要素が挿入された新しいツリーを返します。

うまくいけば、それはあなたがやろうとしていることに関連しています.

于 2010-06-07T15:57:55.843 に答える