変更の葉の値が与えられ

Question

は、再帰的なツリー構造

data Tree = Leaf Int | Node Tree Tree deriving Show 

ある木の構造を維持しながら、私は木の構造を維持する方法でそれを正規化するように、しかしで整数を作るだろう葉は深さ順に連続している。どうすればこれを達成できますか？

myTree = Node (Leaf 3) (Node (Leaf 5) (Leaf 2)) 

myTree' = normalize myTree 

-- preserve tree structure, but make Ints sequential in depths-first traversal 
normalize :: Tree -> Tree 
normalize = id -- todo: implement 

main = do 
    print myTree -- prints  : Node (Leaf 3) (Node (Leaf 5) (Leaf 2)) 
    print myTree' -- should print: Node (Leaf 1) (Node (Leaf 2) (Leaf 3)) 

Answer 1

モナドを使用せずに、あなたが特定の状態

mapLRS :: (s -> Int -> (s, Int)) -> s -> Tree -> (Tree, s) 
mapLRS f s (Leaf x ) = 
    let (s', x') = f s x 
    in (Leaf x', s')     -- the mapped leaf and the new state 
mapLRS f s (Node l r) = 
    let (l', s') = mapLRS f s l  -- the mapped left branch and the new state 
     (r', s'') = mapLRS f s' r  -- the mapped right branch and the new state 
    in (Node l' r', s'') 

今

normalize :: Tree -> Tree 
normalize = fst . mapWithStateLeftRight (\s _ -> (s + 1, s)) 1 

より読みやすいかもしれないモナドを使用してを運ぶ一つの機能マッピング木を書き込むことができます。次のように私の現在のセットアップコードが見えます（簡略化のため、fはstateを使用して同じではありません）

import Control.Monad.State 

mapLRS :: (s -> (Int, s)) -> Tree -> State s Tree 
mapLRS f (Leaf x) = Leaf <$> state f 
mapLRS f (Node l r) = Node <$> mapLRS f l <*> mapLRS f r 

normalize :: Tree -> Tree 
normalize tree = evalState (mapLRS (\s -> (s, s + 1)) tree) 1 

Answer 2

これを行うための標準的な方法は、状態モナドで現在のラベルを記録することです。このソリューションは、1に状態を初期化

import Control.Monad.State 

data Tree = Leaf Int | Node Tree Tree deriving (Show) 

normalize :: Tree -> Tree 
normalize t = evalState (go t) 1 where 

    go :: Tree -> State Int Tree 
    go (Leaf _) = Leaf <$> (get <* modify (+1)) 
    go (Node l r) = Node <$> go l <*> go r 

、その後、ツリーをトラバースし、それぞれの上に、それが現在のラベルを置くLeafに遭遇しました返されたLeafに追加し、ラベルをインクリメントします。

代わりに、我々はTreeためTraversableインスタンスを導き出すことができます。

{-# language DeriveFunctor, DeriveFoldable, DeriveTraversable #-} 

import Control.Monad.State 

data Tree a = Leaf a | Node (Tree a) (Tree a) 
    deriving (Show, Functor, Foldable, Traversable) 

normalize :: Tree a -> Tree Int 
normalize = (`evalState` 1) . traverse (\_ -> get <* modify (+1)) 

をこれは、同じように動作しますが、そのノートには、派生Traversableインスタンスが右トラバーサル順序を持っているという事実に依存していること。もちろん、他の注文が必要な場合は、独自のトラバーサルを作成する必要があります。