0

一般的なケース:
ツリーへの書き込み方法を知りたい (つまり、最下位レベルの特定のノードを変更し、古いノードを左の子とし、新しいノードを右の子とする別の値を持つノードに置き換える)


より困難にしている特定のアプリケーション:
ファイルから既存のツリーを読み取り、ユーザーにさまざまな質問をし、答えがわからない場合はユーザーに質問する 20 の質問に似たゲームをまとめようとしています。最終的な推測と正しい答え、および正しい答えの間の質問を区別し、新しいエントリをゲームに追加します (推測と答えを指すノードで、推測があった位置を新しい質問に置き換えます)。

4

1 に答える 1

4

多くの場合、モナド構造とこの種の木の移植の間には密接な対応があります。これが例です

data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving Functor

instance Monad Tree where
  return = Leaf
  Leaf a >>= f = f a
  Branch l r >>= f = Branch (l >>= f) (r >>= f)

where(>>=)は、何らかの関数に基づいて葉の拡張 (ツリーの移植) を行っているだけですf :: a -> Tree a。

その後、お探しの移植を簡単に行うことができます

graftRight :: Eq a => a -> a -> Tree a -> Tree a
graftRight a new t = t >>= go where
  go a' | a' == a   = Node a new
        | otherwise = Leaf a'

しかし、これは非常に非効率的です。なぜなら、Leaf置換したい特定のものを探してツリー内のすべてを訪問するからです。より多くの情報を知っていれば、より良いことができます。ツリーが何らかの順序で並べ替えられている場合は、fingertreeorを使用splaytreeして効率的な置換を行うことができます。置き換えたいノードがそのパスだけでわかっている場合は、Zipper を使用できます。

data TreeDir = L | R
data ZTree a = Root 
             | Step TreeDir (Tree a) (ZTree a)

これにより、ツリーのルートに出入りできます

stepIn :: Tree a -> (Tree a, ZTree a)
stepIn t = (t, Root)

stepOut :: (Tree a, ZTree a) -> Maybe (Tree a)
stepOut (t, Root) = Just t
stepOut _         = Nothing

中に入ったら、好きな方向に歩いてください

left :: (Tree a, ZTree a) -> Maybe (Tree a, ZTree a)
left (Leaf a, zip) = Nothing
left (Branch l r, zip) = Just (l, Step R r zip)

right :: (Tree a, ZTree a) -> Maybe (Tree a, ZTree a)
right (Leaf a, zip) = Nothing
right (Branch l r, zip) = Just (r, Step L l zip)

up :: (Tree a, ZTree a) -> Maybe (Tree a, ZTree a)
up (tree, Root) = Nothing
up (tree, Step L l zip) = Just (branch l tree, zip)
up (tree, Step R r zip) = Just (branch tree r, zip)

そして葉を編集する

graft :: (a -> Tree a) -> (Tree a, ZTree a) -> Maybe (Tree a, ZTree a)
graft f (Leaf a, zip) = Just (f a, zip)
graft _ _             = Nothing

または、上からのバインドを使用して、特定の場所の下にあるすべての葉を作成することもできます。

graftAll :: (a -> Tree a) -> (Tree a, ZTree a) -> (Tree a, ZTree a)
graftAll f (tree, zip) = (tree >>= f, zip)

そして、移植を行う前に、ツリーの任意のポイントに移動できます

graftBelow :: (a -> Tree a) -> [TreeDir] -> Tree a -> Maybe (Tree a)
graftBelow f steps t = perform (stepIn t) >>= stepOut where
  perform =     foldr (>=>) Just (map stepOf steps)          -- walk all the way down the path
            >=> (Just . graftAll f)                      -- graft here
            >=> foldr (>=>) Just (map (const up) steps)      -- walk back up it
  stepOf L = left
  stepOf R = right

>>> let z = Branch (Branch (Leaf "hello") (Leaf "goodbye"))
                   (Branch (Branch (Leaf "burrito")
                                   (Leaf "falcon"))
                           (Branch (Leaf "taco")
                                   (Leaf "pigeon")))

>>> graftBelow Just [] z == z
True

>>> let dup a = Branch (Leaf a) (Leaf a)
>>> graftBelow dup [L, R] z
Just (Branch (Branch (Leaf "hello") 
                     (Branch (Leaf "goodbye") 
                             (Leaf "goodbye"))) 
             (Branch (Branch (Leaf "burrito") (Leaf "falcon")) 
                     (Branch (Leaf "taco") (Leaf "pigeon"))))

>>> graftBelow dup [L, R, R] z
Nothing

一般に、この目標を達成するには多くの方法があります。

于 2013-10-23T21:53:02.190 に答える