0

したがって、再帰を厳密に使用してBSTの要素に連続番号を追加しようとしています(標準のプレリュード関数はありません)。これが私がこれまでに持っているものです：

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
leaf x = Node x Empty Empty 

number' :: Int -> Tree a -> Tree (Int, a)
number' a Empty = Empty    
number' a (Node x xl xr) = Node (a,x) (number' (a+1) xl) (number' (a+1)  xr) 

number :: Tree a -> Tree (Int, a)
number = number' 1

number' は、「a」をカウンターとして持ち運ぶ補助関数です。再帰呼び出しごとに1を追加する必要があるため、なぜそれが何をしているのかわかりません。現在、要素のレベルは各要素に割り当てられています。最初の要素に 1、その 2 の左側の要素、その 3 の左側の要素などを割り当てたいと思います。各要素には a+1 が割り当てられ、番号は繰り返されません。前もって感謝します。

4

3 に答える 3

2 
data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)

number :: Tree a -> Tree (Int, a)
number = fst . number' 1 

number' :: Int -> Tree a -> (Tree (Int, a), Int)
number' a Empty = (Empty, a)
number' a (Node x l r) = let (l', a') = number' (a + 1) l
                             (r', a'') = number' a' r
                          in (Node (a, x) l' r', a'')

*Tr> let t = (Node 10 (Node 20 (Node 30 Empty Empty) (Node 40 Empty Empty)) (Node 50 (Node 60 Empty Empty) Empty))
*Tr> t
 Node 10 (Node 20 (Node 30 Empty Empty) (Node 40 Empty Empty)) (Node 50 (Node 60 Empty Empty) Empty)
*Tr> number t
Node (1,10) (Node (2,20) (Node (3,30) Empty Empty) (Node (4,40) Empty Empty)) (Node (5,50) (Node (6,60) Empty Empty) Empty)
于 2013-07-12T01:28:16.980 に答える
2

問題のコードがレベル番号を割り当てる理由を最初に説明したいと思います。これにより、2 つの異なるソリューションに直接導かれます。1 つはキャッシュに渡され、もう 1 つは一度に 2 つのトラバーサルを実行することに基づいています。最後に、2 番目の解決策が他の回答によって提供される解決策とどのように関連するかを示します。

質問のコードで何を変更する必要がありますか?

問題のコードは、レベル番号を各ノードに割り当てます。number'関数の再帰ケースを見ると、コードがそのように動作する理由を理解できます。

number' a (Node x xl xr) = Node (a,x) (number' (a+1) xl) (number' (a+1)  xr)

a + 1両方の再帰呼び出しに同じ番号 を使用していることに注意してください。したがって、両方のサブツリーのルート ノードには同じ番号が割り当てられます。各ノードに異なる番号を持たせたい場合は、異なる番号を再帰呼び出しに渡す方がよいでしょう。

再帰呼び出しに渡すべき番号は?

左から右への事前順序トラバーサルに従って番号を割り当てたい場合a + 1、左のサブツリーの再帰呼び出しは正しいですが、右のサブツリーの再帰呼び出しは正しくありません。代わりに、左側のサブツリー全体に注釈を付けるのに十分な数を除外し、次の番号で右側のサブツリーに注釈を付け始めます。

左のサブツリーに予約する必要がある数はいくつですか? これは、この関数によって計算されるサブツリーのサイズによって異なります。

size :: Tree a -> Int
size Empty = 0
size (Node _ xl xr) = 1 + size xl + size xr

関数の再帰ケースに戻りnumber'ます。左のサブツリーのどこかに注釈が付けられている最小の数値はa + 1です。左のサブツリーのどこかに注釈が付けられている最大の数字はa + size xlです。したがって、右のサブツリーで使用できる最小の数は ですa + size xl + 1。number'この推論は、正しく機能する再帰ケースの次の実装につながります。

number' :: Int -> Tree a -> Tree (Int, a)
number' a Empty = Empty    
number' a (Node x xl xr) = Node (a,x) (number' (a+1) xl) (number' (a + size xl + 1)  xr)

残念ながら、このソリューションには問題があります。不必要に遅くなります。

ソリューションがsize遅いのはなぜですか？

関数sizeはツリー全体をトラバースします。この関数number'はツリー全体もトラバースし、sizeすべての左側のサブツリーを呼び出します。これらの各呼び出しは、サブツリー全体をトラバースします。したがって、全体として、関数sizeは同じノードで複数回実行されますが、もちろん常に同じ値が返されます。

を呼び出すときにツリーをトラバースしないようにするにはどうすればよいsizeでしょうか?

私は 2 つの解決策を知っています:sizeすべてのツリーのサイズをキャッシュすることで の実装でツリーをトラバースするのを避けるかsize、ノードに番号を付けて 1 回のトラバースでサイズを計算することで最初の呼び出しを避けるかのいずれかです。

ツリーをトラバースせずにサイズを計算するにはどうすればよいでしょうか?

すべてのツリー ノードにサイズをキャッシュします。

data Tree a = Empty | Node Int a (Tree a) (Tree a) deriving (Show)

size :: Tree a -> Int
size Empty = 0
size (Node n _ _ _) = n

Nodeの場合size、キャッシュされたサイズを返すだけであることに注意してください。したがって、このケースは再帰的でsizeはなく、ツリーをトラバースしませんnumber'。上記の実装の問題は解消されます。

しかし、に関する情報sizeはどこかから来なければなりません! を作成するたびにNode、キャッシュを埋めるために正しいサイズを提供する必要があります。このタスクをスマート コンストラクターに任せることができます。

empty :: Tree a
empty = Empty

node :: a -> Tree a -> Tree a -> Tree a
node x xl xr = Node (size xl + size xr + 1) x xl xr

leaf :: a -> Tree a
leaf x = Node 1 x Empty Empty

node本当に必要なのはOnly だけですが、完全を期すために他の 2 つを追加しました。これら 3 つの関数のいずれかを使用してツリーを作成すると、キャッシュされたサイズ情報は常に正確になります。

number'これらの定義で動作するのバージョンは次のとおりです。

number' :: Int -> Tree a -> Tree (Int, a)
number' a Empty = Empty    
number' a (Node _ x xl xr) = node (a,x) (number' (a+1) xl) (number' (a + size xl + 1)  xr)

2 つのことを調整する必要があります。 でパターン マッチングを行う場合Node、サイズ情報を無視します。を作成するときNodeは、スマート コンストラクターを使用しnodeます。

これは問題なく機能しますが、ツリーの定義を変更しなければならないという欠点があります。いずれにせよ、サイズをキャッシュすることは良い考えかもしれませんが、メモリをいくらか使用し、ツリーを有限にする必要があります。number'ツリーの定義を変更せずに断食を実装したい場合はどうすればよいでしょうか? これにより、私が約束した 2 番目の解決策にたどり着きます。

サイズを計算せずにツリーに番号を付けるにはどうすればよいでしょうか?

できない。しかし、ツリーに番号を付けてサイズを計算することで、1 回のトラバーサルで複数回のsize呼び出しを回避できます。

number' :: Int -> Tree a -> (Int, Tree (Int, a))

すでに型シグネチャで、このバージョンの がnumber'2 つの情報を計算していることがわかります。結果のタプルの最初のコンポーネントはツリーのサイズで、2 番目のコンポーネントは注釈付きツリーです。

number' a Empty = (0, Empty)
number' a (Node x xl xr) = (sl + sr + 1, Node (a, x) yl yr) where
  (sl, yl) = number' (a + 1) xl
  (sr, yr) = number' (a + sl + 1) xr

実装は、再帰呼び出しからタプルを分解し、結果のコンポーネントを構成します。は前のソリューションのようであり、 のようslであることに注意してください。注釈付きサブツリーにも名前を付ける必要があります。はノード番号を持つ左側のサブツリーであるため、前のソリューションと同様であり、ノード番号を持つ右側のサブツリーであるため、前のソリューションと同様です。size xlsrsize xrylnumber' ... xlyrnumber' ... xr

numberの結果の 2 番目のコンポーネントのみを返すように変更する必要もありますnumber'。

number :: Tree a -> Tree (Int, a)
number = snd . number' 1

ある意味、これが最も明確な解決策だと思います。

他に何を改善できるでしょうか？

前のソリューションは、サブツリーのサイズを返すことで機能します。次に、その情報を使用して、次に利用可能なノード番号を計算します。代わりに、次に利用可能なノード番号を直接返すこともできます。

number' a Empty = (a, Empty)
number' a (Node x xl xr) = (ar, Node (a, x) yl yr) where
  (al, yl) = number' (a + 1) xl
  (ar, yr) = number' al xr

は前のソリューションと同様であり、とal同様であることに注意してください。明らかに、この変更によりいくつかの追加が回避されます。a + sl + 1ara + sl + sr + 1

これは本質的にセルゲイの答えからの解決策であり、これがほとんどの Haskeller が作成するバージョンであると期待しています。a、alおよびの操作をar状態モナドで非表示にすることもできますが、そのような小さな例では実際には役に立たないと思います。Ankur による回答は、それがどのように見えるかを示しています。

于 2013-07-12T17:49:16.457 に答える
1

質問のコメントで示唆されているように、各呼び出しnumberは整数を返す必要があり、これは次のノードのセットでさらに使用する必要があります。これにより、関数の署名が次のようになります。

Tree a -> Int -> (Tree (Int,a), Int)

その最後の部分を見ると、State モナド ie の候補のように見えstate -> (Val,state)ます。

以下のコードは、State モナドを使用してこれを行う方法を示しています。

import Control.Monad.State

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)

myTree :: Tree String
myTree = Node "A" (Node "B" (Node "D" Empty Empty) (Node "E" Empty Empty)) (Node "C" (Node "F" Empty Empty) (Node "G" Empty Empty))

inc :: State Int ()
inc = do
  i <- get
  put $ i + 1
  return ()

number :: Tree a -> State Int (Tree (Int,a))
number Empty = return Empty
number (Node x l r) = do
  i <- get
  inc
  l' <- number l
  r' <- number r
  return $ Node (i,x) l' r'

main = do
    putStrLn $ show (fst (runState (number myTree) 1))
于 2013-07-12T05:31:55.663 に答える